#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
 
string A, B;
int dp[1010][1010];
string result;
 
int solve(int aIdx, int bIdx)
{
    if(aIdx == A.size() || bIdx == B.size())
    {
        return 0;
    }
    
    if(dp[aIdx][bIdx] != 0)
    {
        return dp[aIdx][bIdx];
    }
    
    if(A[aIdx] == B[bIdx])
    {
        dp[aIdx][bIdx] = solve(aIdx+1, bIdx+1) + 1;
    }
    else
    {
        dp[aIdx][bIdx] = max(solve(aIdx+1, bIdx), solve(aIdx, bIdx+1));
    }
    
    return dp[aIdx][bIdx];
}
 
int main(void)
{
//    freopen("B9252_input.txt", "r", stdin);
    
    cin >> A >> B;
    
    cout << solve(0, 0) << endl;
 
    int aIdx = 0;
    int bIdx = 0;
    while(dp[aIdx][bIdx] != 0)
    {
        if(dp[aIdx][bIdx] == dp[aIdx+1][bIdx])
        {
            aIdx++;
        }
        else if(dp[aIdx][bIdx] == dp[aIdx][bIdx+1])
        {
            bIdx++;
        }
        else if(dp[aIdx][bIdx]-1 == dp[aIdx+1][bIdx+1])
        {
            result += A[aIdx];
            aIdx++;
            bIdx++;
        }
    }
    
    cout << result << endl;
    
    return 0;
}
cs
저작자표시

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

[백준 1309] 동물원 (DP) (C/C++) (★★)  (0) 2020.03.16
[백준 1965] 상자 넣기 (DP) (C/C++)  (0) 2020.03.16
[백준 9251] LCS (DP) (C/C++)  (0) 2020.03.16
[백준 2163] 초콜릿 자르기 (DP) (C/C++)  (0) 2020.03.15
[백준 1010] 다리 놓기 (DP) (C/C++)  (0) 2020.03.15
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
using namespace std;
 
string A, B;
int dp[1010][1010];
int Max;
 
int solve(int aIdx, int bIdx)
{
    if(aIdx == A.size() || bIdx == B.size())
    {
        return 0;    
    }    
    
    if(dp[aIdx][bIdx] != 0)
    {
        return dp[aIdx][bIdx];
    }
 
    if(A[aIdx] == B[bIdx])
    {
        dp[aIdx][bIdx] = solve(aIdx+1, bIdx+1) + 1;
    }
    else
    {
        dp[aIdx][bIdx] = max(solve(aIdx+1, bIdx), solve(aIdx, bIdx+1));
    }
    
    return dp[aIdx][bIdx];
}
 
int main(void)
{
//    freopen("B9251_input.txt", "r", stdin);
    
    cin >> A >> B;
    
    cout << solve(0, 0);
    
    return 0;
}
cs
저작자표시

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

[백준 1965] 상자 넣기 (DP) (C/C++)  (0) 2020.03.16
[백준 9252] LCS 2 (DP) (C/C++) (★★★)  (0) 2020.03.16
[백준 2163] 초콜릿 자르기 (DP) (C/C++)  (0) 2020.03.15
[백준 1010] 다리 놓기 (DP) (C/C++)  (0) 2020.03.15
[백준 1149] RGB 거리 (DP) (C/C++) (★)  (0) 2020.03.15
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
int N, M;
int dp[310];
 
int solve(int n, int m)
{
    if(n == 1)
    {
        return m-1;    
    }    
    
    if(dp[n] != 0)
    {
        return dp[n];
    }
 
    if(n % 2 == 0)
    {
        dp[n] += solve(n/2, m) + solve(n/2, m) + 1;
    }
    else
    {
        dp[n] += solve(n/2, m) + solve(n/2+1, m) + 1;
    }
    
    return dp[n];
}
 
int main(void)
{
//    freopen("B2163_input.txt", "r", stdin);
    
    cin >> N >> M;
    
    cout << solve(N, M);
    
    return 0;
}
cs
저작자표시

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

[백준 9252] LCS 2 (DP) (C/C++) (★★★)  (0) 2020.03.16
[백준 9251] LCS (DP) (C/C++)  (0) 2020.03.16
[백준 1010] 다리 놓기 (DP) (C/C++)  (0) 2020.03.15
[백준 1149] RGB 거리 (DP) (C/C++) (★)  (0) 2020.03.15
[백준 1932] 정수 삼각형 (DP) (C/C++)  (0) 2020.03.15
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
int T;
int west, east;
long long dp[35][35];
 
long long solve(int e, int w)
{
    if(w == 0 || (e == w))
    {
        return 1;
    }
    
    if(dp[e][w] != 0)
    {
        return dp[e][w];
    }
    
    dp[e][w] = solve(e-1, w-1) + solve(e-1, w);
    
    return dp[e][w];;
}
 
int main(void)
{
//    freopen("B1010_input.txt", "r", stdin);
    
    cin >> T;
    
    while(T--)
    {
        memset(dp, 0, sizeof(dp));
        
        cin >> west >> east;
        
        cout << solve(east, west) << "\n";
    }
    
    return 0;
}
cs
저작자표시

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

[백준 9251] LCS (DP) (C/C++)  (0) 2020.03.16
[백준 2163] 초콜릿 자르기 (DP) (C/C++)  (0) 2020.03.15
[백준 1149] RGB 거리 (DP) (C/C++) (★)  (0) 2020.03.15
[백준 1932] 정수 삼각형 (DP) (C/C++)  (0) 2020.03.15
[백준 1003] 피보나치 함수 (DP) (C/C++)  (0) 2020.03.15
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
int N;
int red[1010];
int blue[1010];
int green[1010];
int dp[3][1010];
 
int solve(int color, int cnt)
{
    if(cnt == N)
    {
        return 0;
    }
    
    if(dp[color][cnt] != 99999999)
    {
        return dp[color][cnt];
    }
    
    if(color == 0)
    {
        dp[color][cnt] = min(solve(1, cnt+1) + red[cnt], solve(2, cnt+1) + red[cnt]);
    }
    else if(color == 1)
    {
        dp[color][cnt] = min(solve(0, cnt+1) + blue[cnt], solve(2, cnt+1) + blue[cnt]);
    }
    else if(color == 2)
    {
        dp[color][cnt] = min(solve(0, cnt+1) + green[cnt], solve(1, cnt+1) + green[cnt]);
    }
    
    return dp[color][cnt];
}
 
int main(void)
{
//    freopen("B1149_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 0; i < N; i++)
    {
        cin >> red[i] >> blue[i] >> green[i];
        
        dp[0][i] = 99999999;
        dp[1][i] = 99999999;
        dp[2][i] = 99999999;
    }
    
    cout << min({solve(0, 0), solve(1, 0), solve(2,0)});
    
    return 0;
}
cs
저작자표시

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

[백준 2163] 초콜릿 자르기 (DP) (C/C++)  (0) 2020.03.15
[백준 1010] 다리 놓기 (DP) (C/C++)  (0) 2020.03.15
[백준 1932] 정수 삼각형 (DP) (C/C++)  (0) 2020.03.15
[백준 1003] 피보나치 함수 (DP) (C/C++)  (0) 2020.03.15
[백준 10211] Maximum Subarray (DP) (C/C++) (★★)  (0) 2020.03.15
#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
int arr[510][510];
int dp[510][510];
 
int solve(int row, int col)
{
    if(row == N)
    {
        return 0;
    }
    
    if(dp[row][col] != 0)
    {
        return dp[row][col];
    }
    
    dp[row][col] = max(solve(row+1, col) + arr[row][col], solve(row+1, col+1) + arr[row][col+1]);
    
    return dp[row][col];
}
 
int main(void)
{
//    freopen("B1932_input.txt", "r", stdin);
    
    cin >> N;
 
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            cin >> arr[i][j];
        }
    }
    
    cout << solve(0, 0);
    
    return 0;
}
cs
저작자표시

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

[백준 1010] 다리 놓기 (DP) (C/C++)  (0) 2020.03.15
[백준 1149] RGB 거리 (DP) (C/C++) (★)  (0) 2020.03.15
[백준 1003] 피보나치 함수 (DP) (C/C++)  (0) 2020.03.15
[백준 10211] Maximum Subarray (DP) (C/C++) (★★)  (0) 2020.03.15
[백준 17485] 진우의 달 여행 (DP) (C/C++) (★)  (0) 2020.03.13
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
int T, N;
int dp0[45];
int dp1[45];
 
int solve0(int n)
{
    if(n == 0)
    {
        return 1;    
    }    
    else if(n == 1)
    {
        return 0;
    }
    
    if(dp0[n] != 0)
    {
        return dp0[n];
    }
 
    dp0[n] = solve0(n-1) + solve0(n-2);
    
    return dp0[n];
}
 
int solve1(int n)
{
    cout << n << endl;
    
    if(n == 0)
    {
        return 0;    
    }    
    else if(n == 1)
    {
        return 1;
    }
    
    if(dp1[n] != 0)
    {
        return dp1[n];
    }
 
    dp1[n] = solve1(n-1) + solve1(n-2);
    
    return dp1[n];
}
 
int main(void)
{
//    freopen("B1003_input.txt", "r", stdin);
    
    cin >> T;
    
    while(T--)
    {
        cin >> N;
        
        cout << solve0(N) << " " << solve1(N) << endl;
    }
    
    return 0;
}
cs
저작자표시

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

[백준 1149] RGB 거리 (DP) (C/C++) (★)  (0) 2020.03.15
[백준 1932] 정수 삼각형 (DP) (C/C++)  (0) 2020.03.15
[백준 10211] Maximum Subarray (DP) (C/C++) (★★)  (0) 2020.03.15
[백준 17485] 진우의 달 여행 (DP) (C/C++) (★)  (0) 2020.03.13
[백준 12865] 평범한 배낭 (DP) (C/C++) (★)  (0) 2020.03.13
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
int T, N;
int dp[1010];
int arr[1010];
 
int main(void)
{
//    freopen("B10211_input.txt", "r", stdin);
    
    cin >> T;
    
    while(T--)
    {
        cin    >> N;
        
        for(int i = 1; i <= N; i++)
        {
            cin >> arr[i];
        }
        
        int Max = -99999999;
 
        for(int i = 1; i <= N; i++)
        {
            dp[i] = max(0, dp[i-1]) + arr[i];
            Max = max(Max, dp[i]);
        }
        
        cout << Max << endl;
    }
    
    return 0;
}
cs
저작자표시

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

[백준 1932] 정수 삼각형 (DP) (C/C++)  (0) 2020.03.15
[백준 1003] 피보나치 함수 (DP) (C/C++)  (0) 2020.03.15
[백준 17485] 진우의 달 여행 (DP) (C/C++) (★)  (0) 2020.03.13
[백준 12865] 평범한 배낭 (DP) (C/C++) (★)  (0) 2020.03.13
[백준 1480] 보석 모으기 (DP, Bitmask) (C/C++) (★★★)  (0) 2020.03.13

+ Recent posts

티스토리툴바