#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
int N;
int map[100010][3];
int dp_max[2][3];
int dp_min[2][3];
 
int main(void)
{
//    freopen("B2096_input.txt", "r", stdin);
    
    cin >> N;
 
    for(int i = 0; i < N; i++)
    {
        cin >> map[i][0] >> map[i][1] >> map[i][2];
        
        dp_max[1][0] = map[i][0] + max(dp_max[0][0], dp_max[0][1]);
        dp_max[1][1] = map[i][1] + max({dp_max[0][0], dp_max[0][1], dp_max[0][2]});
        dp_max[1][2] = map[i][2] + max(dp_max[0][1], dp_max[0][2]);
        
        dp_max[0][0] = dp_max[1][0];
        dp_max[0][1] = dp_max[1][1];
        dp_max[0][2] = dp_max[1][2];
        
        dp_min[1][0] = map[i][0] + min(dp_min[0][0], dp_min[0][1]);
        dp_min[1][1] = map[i][1] + min({dp_min[0][0], dp_min[0][1], dp_min[0][2]});
        dp_min[1][2] = map[i][2] + min(dp_min[0][1], dp_min[0][2]);
        
        dp_min[0][0] = dp_min[1][0];
        dp_min[0][1] = dp_min[1][1];
        dp_min[0][2] = dp_min[1][2];
    }
 
    cout << max({dp_max[0][0], dp_max[0][1], dp_max[0][2]}) << " " << min({dp_min[0][0], dp_min[0][1], dp_min[0][2]});
    
    return 0;
}
cs
저작자표시

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

[백준 9507] Generations of Tribbles (DP) (C/C++)  (0) 2020.03.22
[백준 1904] 타일 (DP) (C/C++)  (0) 2020.03.22
[백준 1915] 가장 큰 정사각형 찾기 (DP) (C/C++) (★)  (0) 2020.03.17
[백준 11051] 이항 계수 2 (DP) (C/C++)  (0) 2020.03.17
[백준 2186] 문자판 (DFS, DP) (C/C++) (★★★)  (0) 2020.03.17
#include <iostream>
#include <algorithm>
using namespace std;
 
int row, col;
int map[1010][1010];
int Max;
 
int main(void)
{
//    freopen("B1915_input.txt", "r", stdin);
    
    cin >> row >> col;
    
    for(int i = 1; i <= row; i++)
    {
        for(int j = 1; j <= col; j++)
        {
            scanf("%1d", &map[i][j]);    
        }
    }
    
    if(row == 1 || col == 1)
    {
        for(int i = 1; i <= row; i++)
        {
            for(int j = 1; j <= col; j++)
            {
                if(map[i][j] == 1)
                {
                    Max = 1;
                    break;
                }
            }
        }
    }
    else
    {
        for(int i = 1; i <= row; i++)
        {
            for(int j = 1; j <= col; j++)
            {
                if(map[i][j] != 0)
                {
                    map[i][j] = min({map[i-1][j], map[i][j-1], map[i-1][j-1]}) + 1;
                    Max = max(Max, map[i][j]);
                }
            }
        }    
    }
    
    cout << Max * Max;
    
    return 0;
}
cs
저작자표시

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

[백준 1904] 타일 (DP) (C/C++)  (0) 2020.03.22
[백준 2096] 내려가기 (DP) (C/C++) (★★)  (0) 2020.03.22
[백준 11051] 이항 계수 2 (DP) (C/C++)  (0) 2020.03.17
[백준 2186] 문자판 (DFS, DP) (C/C++) (★★★)  (0) 2020.03.17
[백준 1520] 내리막 길 (DFS, DP) (C/C++) (★★)  (0) 2020.03.17
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
int N, K;
int dp[1010][1010];
 
int solve(int n, int k)
{
    if(k == 0 || n == k)
    {
        return 1;
    }
    
    if(dp[n][k] != 0)
    {
        return dp[n][k] % 10007;
    }
    
    dp[n][k] = solve(n-1, k-1) + solve(n-1, k);
    
    return dp[n][k] % 10007;
}
 
int main(void)
{
//    freopen("B11051_input.txt", "r", stdin);
 
    cin >> N >> K;
    
    cout << solve(N, K);
    
    return 0;
}
cs
저작자표시

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

[백준 2096] 내려가기 (DP) (C/C++) (★★)  (0) 2020.03.22
[백준 1915] 가장 큰 정사각형 찾기 (DP) (C/C++) (★)  (0) 2020.03.17
[백준 2186] 문자판 (DFS, DP) (C/C++) (★★★)  (0) 2020.03.17
[백준 1520] 내리막 길 (DFS, DP) (C/C++) (★★)  (0) 2020.03.17
[백준 1937] 욕심쟁이 판다 (DFS, DP) (C/C++) (★)  (0) 2020.03.16
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <string>
#include <string.h>
using namespace std;
 
int row, col, K;
char Map[110][110];
int dp[110][110][90];
string word;
int ans;
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && x < row && y >= 0 && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
int DFS(int x, int y, int idx)
{
    if(Map[x][y] == word[idx] && idx == word.size()-1)
    {
        return 1;
    }
    
    // dp[x][y][idx] != 0 이면 시간초과 -> dp[x][y][idx] = 0 인 경우에는 어차피 더 찾아도 없음을 뜻함 중요.. 
    if(dp[x][y][idx] != -1)
    {
        return dp[x][y][idx];
    }
    
    dp[x][y][idx] = 0; 
    
    for(int i = 0; i < 4; i++)
    {
        for(int j = 1; j <= K; j++)
        {
            int xpos = x + (dx[i] * j);
            int ypos = y + (dy[i] * j);    
            int nIdx = idx + 1;    
            
            if(safe(xpos, ypos) == 1 && Map[xpos][ypos] == word[nIdx])
            {
                dp[x][y][idx] += DFS(xpos, ypos, nIdx);
            }
        }
    }
    
    return dp[x][y][idx];
}
 
int main(void)
{
//    freopen("B2186_input.txt", "r", stdin);
    
    cin >> row >> col >> K;
    
    for(int i = 0; i < row; i++)
    {
        string temp;
        cin >> temp;
        
        for(int j = 0; j < temp.size(); j++)
        {
            Map[i][j] = temp[j];
        }
    }
    
    cin >> word;
    
    memset(dp, -1, sizeof(dp));
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(Map[i][j] == word[0])
            {
                ans += DFS(i, j, 0);
            }
        }
    }
    
    cout << ans;
    
    return 0;
}
cs
저작자표시

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

[백준 1915] 가장 큰 정사각형 찾기 (DP) (C/C++) (★)  (0) 2020.03.17
[백준 11051] 이항 계수 2 (DP) (C/C++)  (0) 2020.03.17
[백준 1520] 내리막 길 (DFS, DP) (C/C++) (★★)  (0) 2020.03.17
[백준 1937] 욕심쟁이 판다 (DFS, DP) (C/C++) (★)  (0) 2020.03.16
[백준 1309] 동물원 (DP) (C/C++) (★★)  (0) 2020.03.16
#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
 
int map[510][510];
int dp[510][510];
int row, col;
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < row && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
int DFS(int x, int y)
{
    if(x == row-1 && y == col-1)
    {
        return 1;
    }
    
    if(dp[x][y] != -1)
    {
        return dp[x][y];
    }
    
    dp[x][y] = 0;
    
    for(int i = 0; i < 4; i++)
    {
        int xpos = x+dx[i];
        int ypos = y+dy[i];
        
        if(safe(xpos, ypos) == 1)
        {
            if(map[x][y] > map[xpos][ypos])
            {
                dp[x][y] += DFS(xpos, ypos);
            }
        }
    }
    
    return dp[x][y];
}
 
int main(void)
{
//    freopen("B1520_input.txt", "r", stdin);
 
    cin >> row >> col;
 
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> map[i][j];
            dp[i][j] = -1;
        }
    }
    
    cout << DFS(0, 0);
    
    return 0;
}
cs
저작자표시

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

[백준 11051] 이항 계수 2 (DP) (C/C++)  (0) 2020.03.17
[백준 2186] 문자판 (DFS, DP) (C/C++) (★★★)  (0) 2020.03.17
[백준 1937] 욕심쟁이 판다 (DFS, DP) (C/C++) (★)  (0) 2020.03.16
[백준 1309] 동물원 (DP) (C/C++) (★★)  (0) 2020.03.16
[백준 1965] 상자 넣기 (DP) (C/C++)  (0) 2020.03.16
#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
 
int N;
int map[510][510];
int dp[510][510];
int Max;
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < N && y < N)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
int DFS(int x, int y)
{
    if(dp[x][y] != 0)
    {
        return dp[x][y];
    }
    
    dp[x][y] = 1;
    
    for(int i = 0; i < 4; i++)
    {
        int xpos = x+dx[i];
        int ypos = y+dy[i];
        
        if(safe(xpos, ypos) == 1)
        {
            if(map[x][y] < map[xpos][ypos])
            {
                dp[x][y] = max(dp[x][y], DFS(xpos, ypos) + 1);
            }
        }
    }
    
    return dp[x][y];
}
 
int main(void)
{
//    freopen("B1937_input.txt", "r", stdin);
    
    cin >> N;
 
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            cin >> map[i][j];
        }
    }
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            Max = max(Max,  DFS(i, j));
        }
    }
    
    cout << Max;
    
    return 0;
}
 
cs
저작자표시

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

[백준 2186] 문자판 (DFS, DP) (C/C++) (★★★)  (0) 2020.03.17
[백준 1520] 내리막 길 (DFS, DP) (C/C++) (★★)  (0) 2020.03.17
[백준 1309] 동물원 (DP) (C/C++) (★★)  (0) 2020.03.16
[백준 1965] 상자 넣기 (DP) (C/C++)  (0) 2020.03.16
[백준 9252] LCS 2 (DP) (C/C++) (★★★)  (0) 2020.03.16
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
int N;
int dp[100010][3]; // 0(사자X), 1(사자 왼쪽), 2(사자 오른쪽)
 
int solve(int row, int status)
{
    if(row == N)
    {
        return 1;
    }
    
    if(dp[row][status] !=0)
    {
        return dp[row][status];
    }
    
    if(status == 0)
    {
        dp[row][status] += (solve(row+1, 0) + solve(row+1, 1) + solve(row+1, 2)) % 9901;        
    }
    else if(status == 1)
    {
        dp[row][status] += (solve(row+1, 0) + solve(row+1, 2)) % 9901;        
    }
    else if(status == 2)
    {
        dp[row][status] += (solve(row+1, 0) + solve(row+1, 1)) % 9901;    
    }
    
    return dp[row][status] % 9901;
}
 
int main(void)
{
//    freopen("B1309_input.txt", "r", stdin);
    
    cin >> N;
    
    cout << solve(0, 0);
    
    return 0;
}
cs
저작자표시

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

[백준 1520] 내리막 길 (DFS, DP) (C/C++) (★★)  (0) 2020.03.17
[백준 1937] 욕심쟁이 판다 (DFS, DP) (C/C++) (★)  (0) 2020.03.16
[백준 1965] 상자 넣기 (DP) (C/C++)  (0) 2020.03.16
[백준 9252] LCS 2 (DP) (C/C++) (★★★)  (0) 2020.03.16
[백준 9251] LCS (DP) (C/C++)  (0) 2020.03.16
#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
int arr[1010];
int dp[1010];
int Max;
 
int solve(int cnt)
{
    if(dp[cnt] != 0)
    {
        return dp[cnt];
    }
    
    dp[cnt] = 1;
 
    for(int i = cnt-1; i >= 1; i--)
    {
        if(arr[cnt] > arr[i])
        {
            dp[cnt] = max(dp[cnt], solve(i) + 1);
        }
    }
    
    return dp[cnt];
}
 
int main(void)
{
//    freopen("B1965_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' 카테고리의 다른 글

[백준 1937] 욕심쟁이 판다 (DFS, DP) (C/C++) (★)  (0) 2020.03.16
[백준 1309] 동물원 (DP) (C/C++) (★★)  (0) 2020.03.16
[백준 9252] LCS 2 (DP) (C/C++) (★★★)  (0) 2020.03.16
[백준 9251] LCS (DP) (C/C++)  (0) 2020.03.16
[백준 2163] 초콜릿 자르기 (DP) (C/C++)  (0) 2020.03.15

+ Recent posts

티스토리툴바