#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
#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' 카테고리의 다른 글

[백준 11054] 가장 긴 바이토닉 부분 수열 (DP) (C/C++) (★★★)  (0) 2020.01.17
[백준 11722] 가장 긴 감소하는 부분 수열 (DP) (C/C++) (★★)  (0) 2020.01.17
[백준 11053] 가장 긴 증가하는 부분 수열 (DP) (C/C++) (★★)  (0) 2020.01.17
[백준 2156] 포도주 시식 (DP) (C/C++) (★)  (0) 2020.01.17
[백준 9465] 스티커 (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 dp[1010];
 
int solve(int cnt)
{
    if(dp[cnt] != 0)
    {
        return dp[cnt];
    }
    
    dp[cnt] = 1;
    for(int i = cnt-1; i >= 1; i--)
    {
        if(arr[i] < arr[cnt])
        {
            dp[cnt] = max(dp[cnt], solve(i) + 1);        
        }
    }
    
    return dp[cnt];
}
 
int main(void)
{
//    freopen("B11053_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' 카테고리의 다른 글

[백준 11722] 가장 긴 감소하는 부분 수열 (DP) (C/C++) (★★)  (0) 2020.01.17
[백준 11055] 가장 큰 증가 부분 수열 (DP) (C/C++) (★★)  (0) 2020.01.17
[백준 2156] 포도주 시식 (DP) (C/C++) (★)  (0) 2020.01.17
[백준 9465] 스티커 (DP) (C/C++) (★)  (0) 2020.01.17
[백준 2193] 이친수 (DP) (C/C++)  (0) 2020.01.17
#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
int grape[10010];
int dp[10010][3];
 
int solve(int cnt, int chain)
{
    if(cnt <= 0 || chain == 3)
    {
        return 0;
    }
    else if(cnt == 1)
    {
        return grape[cnt];
    }
    
    if(dp[cnt][chain] != 0)
    {
        return dp[cnt][chain];
    }
    
    // 1. 지금것을 안먹고 넘어가는 경우, 2. 지금것도 먹고 다음것도 먹는 경우, 3. 지금것은 먹고 다음것은 안먹는 경우
    dp[cnt][chain] = max({solve(cnt-1, 1), solve(cnt-1, chain+1) + grape[cnt], solve(cnt-2, 1) + grape[cnt]}); 
    
    return dp[cnt][chain];
}
 
int main(void)
{
//    freopen("B2156_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        cin >> grape[i];
    }
    
    cout << solve(N, 1);
    
    return 0;
}
cs
저작자표시 (새창열림)

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

[백준 11055] 가장 큰 증가 부분 수열 (DP) (C/C++) (★★)  (0) 2020.01.17
[백준 11053] 가장 긴 증가하는 부분 수열 (DP) (C/C++) (★★)  (0) 2020.01.17
[백준 9465] 스티커 (DP) (C/C++) (★)  (0) 2020.01.17
[백준 2193] 이친수 (DP) (C/C++)  (0) 2020.01.17
[백준 11057] 오르막 수 (DP) (C/C++) (★)  (0) 2020.01.17
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
int N;
int T;
int dp[100010][2];
int sticker[100010][2];
 
int solve(int cnt, int row)
{
    if(cnt <= 0)
    {
        return 0;
    }
    
    if(dp[cnt][row] != -1)
    {
        return dp[cnt][row];
    }
    
    if(row == 0)
    {
        dp[cnt][row] = max({solve(cnt-2, 0), solve(cnt-2, 1), solve(cnt-1, 1)}) + sticker[cnt][row];
    }
    else
    {
        dp[cnt][row] = max({solve(cnt-2, 1), solve(cnt-2, 0), solve(cnt-1, 0)}) + sticker[cnt][row];
    }
    
    return dp[cnt][row];
}
 
int main(void)
{
//    freopen("B9465_input.txt", "r", stdin);
    
    cin >> T;
    
    for(int i = 1; i <= T; i++)
    {
        cin >> N;
        
        memset(dp, -1, sizeof(dp));
        
        // 1행 
        for(int j = 1; j <= N; j++)
        {
            cin >> sticker[j][0];
        }
        
        // 2행 
        for(int j = 1; j <= N; j++)
        {
            cin >> sticker[j][1];
        }
    
        cout << max(solve(N, 0), solve(N, 1)) << endl;
    }
    
    return 0;
}
 cs
저작자표시 (새창열림)

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

[백준 11053] 가장 긴 증가하는 부분 수열 (DP) (C/C++) (★★)  (0) 2020.01.17
[백준 2156] 포도주 시식 (DP) (C/C++) (★)  (0) 2020.01.17
[백준 2193] 이친수 (DP) (C/C++)  (0) 2020.01.17
[백준 11057] 오르막 수 (DP) (C/C++) (★)  (0) 2020.01.17
[백준 10844] 쉬운 계단수 (DP) (C/C++)  (0) 2020.01.17
#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
long long dp[100][2];
 
long long solve(int cnt, int num)
{
    if(cnt == 1)
    {
        return num == 0 ? 0 : 1;
    }
    
    if(dp[cnt][num] != 0)
    {
        return dp[cnt][num];
    }
    
    if(num == 1)
    {
        dp[cnt][num] = solve(cnt-1, 0);
    }
    else
    {
        dp[cnt][num] = solve(cnt-1, 0) + solve(cnt-1, 1);
    }
    
    return dp[cnt][num];
}
 
int main(void)
{
//    freopen("B2193_input.txt", "r", stdin);
    
    cin >> N;
    
    cout << solve(N, 0) + solve(N, 1); 
    
    return 0;
}
cs
저작자표시 (새창열림)

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

[백준 2156] 포도주 시식 (DP) (C/C++) (★)  (0) 2020.01.17
[백준 9465] 스티커 (DP) (C/C++) (★)  (0) 2020.01.17
[백준 11057] 오르막 수 (DP) (C/C++) (★)  (0) 2020.01.17
[백준 10844] 쉬운 계단수 (DP) (C/C++)  (0) 2020.01.17
[백준 9095] 1, 2, 3 더하기 (DP) (C/C++)  (0) 2020.01.16
#include <iostream>
#include <algorithm>
using namespace std;
 
#define MOD 10007
 
int N;
int sum;
int dp[1010][11];
 
int solve(int cnt, int num)
{
    if(cnt == 1)
    {
        return 1;
    }
    
    if(dp[cnt][num] != 0)
    {
        return dp[cnt][num];
    }
 
    for(int i = num; i >= 0; i--)
    {
        dp[cnt][num] = (dp[cnt][num] + solve(cnt-1, i)) % MOD;    
    }
    
    return dp[cnt][num];
}
 
int main(void)
{
//    freopen("B11057_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 0; i <= 9; i++)
    {
        sum = (sum + solve(N, i)) % MOD;     
    }
    
    cout << sum;
    
    return 0;
}
cs
저작자표시 (새창열림)

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

[백준 9465] 스티커 (DP) (C/C++) (★)  (0) 2020.01.17
[백준 2193] 이친수 (DP) (C/C++)  (0) 2020.01.17
[백준 10844] 쉬운 계단수 (DP) (C/C++)  (0) 2020.01.17
[백준 9095] 1, 2, 3 더하기 (DP) (C/C++)  (0) 2020.01.16
[백준 11727] 2xN 타일링2 (DP) (C/C++)  (0) 2020.01.16

+ Recent posts

티스토리툴바