#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
long long dp[110];
 
long long solve(int num)
{
    if(1 <= num && num <= 3)
    {
        return 1;
    }
    else if(4 <= num && num <= 5)
    {
        return 2;
    }
    
    if(dp[num] != 0)
    {
        return dp[num];
    }
    
    dp[num] = solve(num-1) + solve(num-5);
    
    return dp[num];
}
 
int main(void)
{
//    freopen("B9461_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        int temp;
        cin >> temp;
        
        cout << solve(temp) << endl;    
    }
    
    return 0;
}
cs
저작자표시

'Baekjoon > DP' 카테고리의 다른 글

[백준 11052] 카드 구매하기 (DP) (C/C++)  (0) 2020.01.22
[백준 2011] 암호코드 (DP) (C/C++) (★)  (0) 2020.01.22
[백준 2225] 합분해 (DP) (C/C++)  (0) 2020.01.22
[백준 2133] 타일 채우기 (DP) (C/C++) (★★★)  (0) 2020.01.21
[백준 1699] 제곱수의 합 (DP) (C/C++)  (0) 2020.01.21
#include <iostream>
#include <algorithm>
using namespace std;
 
#define MOD 1000000000
 
int N, K;
long long dp[210][210];
 
int solve(int sum, int cnt)
{
    if(cnt > K || sum > N)
    {
        return 0;
    }
    
    if(cnt == K && sum == N)
    {
        return 1;
    }
    
    if(dp[sum][cnt] != 0)
    {
        return dp[sum][cnt];
    }
 
    for(int i = 0; i <= N; i++)
    {
        dp[sum][cnt] = (dp[sum][cnt] + solve(sum+i, cnt+1)) % MOD;
    }
    
    return dp[sum][cnt];
}
 
int main(void)
{
//    freopen("B2225_input.txt", "r", stdin);
    
    cin >> N >> K;
    
    cout << solve(0, 0);
    
    return 0;
}
cs
저작자표시

'Baekjoon > DP' 카테고리의 다른 글

[백준 2011] 암호코드 (DP) (C/C++) (★)  (0) 2020.01.22
[백준 9461] 파도반 수열(DP) (C/C++)  (0) 2020.01.22
[백준 2133] 타일 채우기 (DP) (C/C++) (★★★)  (0) 2020.01.21
[백준 1699] 제곱수의 합 (DP) (C/C++)  (0) 2020.01.21
[백준 2579] 계단 오르기 (DP) (C/C++)  (0) 2020.01.18
#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
int dp[35];
 
int solve(int num)
{
    if(num == 0)
    {
        return 1;
    }
    else if(num == 2)
    {
        return 3;
    }
    
    if(dp[num] != 0)
    {
        return dp[num];
    }
    
    dp[num] = solve(num-2)*3;
    
    for(int i = num; i >= 4; i -= 2)
    {
        dp[num] += solve(i-4)*2;
    }
    
    return dp[num];
}
 
int main(void)
{
//    freopen("B2133_input.txt", "r", stdin);
    
    cin >> N;
    
    if(N % 2 == 1)
    {
        cout << 0;
    }
    else
    {
        cout << solve(N);    
    }
    
    return 0;
}
cs
저작자표시

'Baekjoon > DP' 카테고리의 다른 글

[백준 9461] 파도반 수열(DP) (C/C++)  (0) 2020.01.22
[백준 2225] 합분해 (DP) (C/C++)  (0) 2020.01.22
[백준 1699] 제곱수의 합 (DP) (C/C++)  (0) 2020.01.21
[백준 2579] 계단 오르기 (DP) (C/C++)  (0) 2020.01.18
[백준 1912] 연속합 (DP) (C/C++) (★)  (0) 2020.01.18
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
 
int N;
int dp[100010];
 
int solve(int num)
{
    if(num == 0)
    {
        return 0;
    }
    
    if(dp[num] != 999999)
    {
        return dp[num];
    }
    
    for(int i = sqrt(num); i >= 1; i--)
    {
        int squared = pow(i, 2);
        
        dp[num] = min(dp[num], solve(num-squared)+1);
    }
    
    return dp[num];
}
 
int main(void)
{
//    freopen("B1699_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 0; i < 100010; i++)
    {
        dp[i] = 999999;
    }
    
    cout << solve(N);
    
    return 0;
}
cs
저작자표시

'Baekjoon > DP' 카테고리의 다른 글

[백준 2225] 합분해 (DP) (C/C++)  (0) 2020.01.22
[백준 2133] 타일 채우기 (DP) (C/C++) (★★★)  (0) 2020.01.21
[백준 2579] 계단 오르기 (DP) (C/C++)  (0) 2020.01.18
[백준 1912] 연속합 (DP) (C/C++) (★)  (0) 2020.01.18
[백준 11054] 가장 긴 바이토닉 부분 수열 (DP) (C/C++) (★★★)  (0) 2020.01.17
#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
int arr[310];
int dp[310][3];
 
int solve(int cnt, int chain)
{
    if(cnt < 1 || chain == 3)
    {
        return 0;
    }
    else if(cnt == 1)
    {
        return arr[cnt];
    }
    
    if(dp[cnt][chain] != 0)
    {
        return dp[cnt][chain];
    }
    
    dp[cnt][chain] = max(solve(cnt-1, chain+1) + arr[cnt], solve(cnt-2, 1) + arr[cnt]);     
    
    return dp[cnt][chain];
}
 
int main(void)
{
//    freopen("B2579_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        cin >> arr[i];
    }
    
    cout << solve(N, 1) << endl;
    
    return 0;
}
cs
저작자표시

'Baekjoon > DP' 카테고리의 다른 글

[백준 2133] 타일 채우기 (DP) (C/C++) (★★★)  (0) 2020.01.21
[백준 1699] 제곱수의 합 (DP) (C/C++)  (0) 2020.01.21
[백준 1912] 연속합 (DP) (C/C++) (★)  (0) 2020.01.18
[백준 11054] 가장 긴 바이토닉 부분 수열 (DP) (C/C++) (★★★)  (0) 2020.01.17
[백준 11722] 가장 긴 감소하는 부분 수열 (DP) (C/C++) (★★)  (0) 2020.01.17
#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
int Max = -99999999;
int arr[100010];
int dp[100010];
 
int solve(int cnt)
{
    if(cnt == 0)
    {
        return 0;
    }
    
    if(dp[cnt] != -1111)
    {
        return dp[cnt];
    }
    
    dp[cnt] = arr[cnt];
    dp[cnt] = max(dp[cnt], dp[cnt] + solve(cnt-1));    
    
    return dp[cnt];
}
 
int main(void)
{
//    freopen("B1912_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        cin >> arr[i];
        dp[i] = -1111;
    }
    
//    for(int i = N; i >= 1; i--)
//    {
//        Max = max(Max, solve(i));    
//    }
 
    solve(N);
    for(int i = 1; i <= N; i++)
    {
        if(Max < dp[i])
        {
            Max = dp[i];
        }
    }
    
    cout << Max;
    
    return 0;
}
cs
저작자표시

'Baekjoon > DP' 카테고리의 다른 글

[백준 1699] 제곱수의 합 (DP) (C/C++)  (0) 2020.01.21
[백준 2579] 계단 오르기 (DP) (C/C++)  (0) 2020.01.18
[백준 11054] 가장 긴 바이토닉 부분 수열 (DP) (C/C++) (★★★)  (0) 2020.01.17
[백준 11722] 가장 긴 감소하는 부분 수열 (DP) (C/C++) (★★)  (0) 2020.01.17
[백준 11055] 가장 큰 증가 부분 수열 (DP) (C/C++) (★★)  (0) 2020.01.17
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
 
int N;
int Max;
int arr[1010];
int dp1[1010];
int dp2[1010];
 
// 증가수열
int solve1(int cnt)
{
    if(dp1[cnt] != 0)
    {
        return dp1[cnt];
    }
    
    dp1[cnt] = 1;
    for(int i = cnt-1; i >= 1; i--)
    {
        if(arr[i] < arr[cnt])
        {
            dp1[cnt] = max(dp1[cnt], solve1(i) + 1);        
        }    
    }
    
    return dp1[cnt];
}
 
// 감소수열 
int solve2(int cnt)
{
    if(dp2[cnt] != 0)
    {
        return dp2[cnt];
    }
    
    dp2[cnt] = 1;
    for(int i = cnt+1; i <= N; i++)
    { 
        if(arr[i] < arr[cnt])
        {
            dp2[cnt] = max(dp2[cnt], solve2(i) + 1);
        }
    }
    
    return dp2[cnt];
}
 
int main(void)
{
//    freopen("B11054_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        cin >> arr[i];
    }
 
    for(int i = N; i >= 1; i--)
    {
        solve1(i);
    }
    
    for(int i = 0; i <= N; i++)
    {
        solve2(i);    
    }
 
    for(int i = 1; i <= N; i++)
    {
        if(Max < dp1[i] + dp2[i])
        {
            Max = dp1[i] + dp2[i];
        }        
    }    
    
    cout << Max-1;
    
    return 0;
}
cs
저작자표시

'Baekjoon > DP' 카테고리의 다른 글

[백준 2579] 계단 오르기 (DP) (C/C++)  (0) 2020.01.18
[백준 1912] 연속합 (DP) (C/C++) (★)  (0) 2020.01.18
[백준 11722] 가장 긴 감소하는 부분 수열 (DP) (C/C++) (★★)  (0) 2020.01.17
[백준 11055] 가장 큰 증가 부분 수열 (DP) (C/C++) (★★)  (0) 2020.01.17
[백준 11053] 가장 긴 증가하는 부분 수열 (DP) (C/C++) (★★)  (0) 2020.01.17
#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
int Max;
int arr[1010];
int dp[1010];
 
int solve(int cnt)
{
    if(dp[cnt] != 0)
    {
        return dp[cnt];
    }
 
    dp[cnt] = arr[cnt];
    for(int i = cnt-1; i >= 1; i--)
    {
        if(arr[i] < arr[cnt])
        {
            dp[cnt] = max(dp[cnt], solve(i) + arr[cnt]);        
        }
    }
    
    return dp[cnt];
}
 
int main(void)
{
//    freopen("B11055_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        cin >> arr[i];
    }
    
    for(int i = N; i >= 1; i--)
    {
        Max = max(Max, solve(i));    
    }
    
    cout << Max;
    
    return 0;
}
cs
저작자표시

'Baekjoon > DP' 카테고리의 다른 글

[백준 1912] 연속합 (DP) (C/C++) (★)  (0) 2020.01.18
[백준 11054] 가장 긴 바이토닉 부분 수열 (DP) (C/C++) (★★★)  (0) 2020.01.17
[백준 11055] 가장 큰 증가 부분 수열 (DP) (C/C++) (★★)  (0) 2020.01.17
[백준 11053] 가장 긴 증가하는 부분 수열 (DP) (C/C++) (★★)  (0) 2020.01.17
[백준 2156] 포도주 시식 (DP) (C/C++) (★)  (0) 2020.01.17

+ Recent posts

티스토리툴바