#include <stdio.h>
#include <iostream>
#include <queue>
#include <map>
#include <string>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
 
int N, M, K;
int road[400][400];
int dp[400][400];
 
int solve(int from, int cnt)
{
    // N에 도착시 종료 
    if(from == N)
    {
        return 0;
    }
    
    // M개의 도시를 전부돌았지만 최종 도착지가 N이 아니면 매우 작은 값 리턴  
    if(cnt >= M)
    {
        return -987654321;    
    }
    
    if(dp[from][cnt] != 0)
    {
        return dp[from][cnt];
    }
    dp[from][cnt] = -987654321;
    
    for(int to = from+1; to <= N; to++)
    {
        if(road[from][to] != 0)
        {
            dp[from][cnt] = max(dp[from][cnt], solve(to, cnt+1) + road[from][to]);
        }
    }
    
    return dp[from][cnt];
}
 
int main(void)
{
//    freopen("B2096_input.txt", "r", stdin);
    
    cin >> N >> M >> K;
    
    for(int i = 1; i <= K; i++)
    {
        int from, to, grade;
        cin >> from >> to >> grade;
        
        if(road[from][to] != 0)
        {
            road[from][to] = max(road[from][to], grade);    
        }
        else
        {
            road[from][to] = grade;
        }
    }
    
    cout << solve(1, 1) << "\n";
 
    return 0;
}
cs
저작자표시

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

[백준 2167] 2차원 배열의 합 (DP) (C/C++) (★★)  (0) 2020.05.28
[백준 1509] 팰린드롬 분할 (DP) (C/C++) (★★★)  (0) 2020.03.24
[백준 10942] 팰린드롬 ? (DP) (C/C++) (★★)  (0) 2020.03.23
[백준 11048] 이동하기 (DFS, DP) (C/C++) (★)  (0) 2020.03.23
[백준 1890] 점프 (DFS, DP) (C/C++)  (0) 2020.03.22
#include <iostream>
#include <algorithm>
#include <math.h>
#include <algorithm>
using namespace std;
 
int N, M, K;
int arr[310][310];
long long dp[310][310];
int startX, startY;
int endX, endY;
 
int main(void)
{
//    freopen("B2167_input.txt", "r", stdin);
    
    cin >> N >> M;
    
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= M; j++)
        {
            cin >> arr[i][j];
        }
    }
    
    // 미리 구해놓기
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= M; j++)
        {
            dp[i][j] = dp[i-1][j] + dp[i][j-1] + arr[i][j] - dp[i-1][j-1];        
        }
    } 
    
    cin >> K;
    
    for(int i = 1; i <= K; i++)
    {
        cin >> startX >> startY >> endX >> endY;
        
        // 좌표가 사각형 기준 오른쪽위, 왼쪽 아래인 경우 -> 왼쪽 위, 오른쪽 아래로 좌표 수정 
        int sx = min(startX, endX);
        int sy = min(startY, endY);
        int ex = max(startX, endX);
        int ey = max(startY, endY);
        
        cout << dp[ex][ey] - dp[sx-1][ey] - dp[ex][sy-1] + dp[sx-1][sy-1] << endl;
    }
    
    return 0;
}
cs
저작자표시

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

[백준 2157] 여행 (DP) (C/C++) (★★★)  (0) 2021.01.26
[백준 1509] 팰린드롬 분할 (DP) (C/C++) (★★★)  (0) 2020.03.24
[백준 10942] 팰린드롬 ? (DP) (C/C++) (★★)  (0) 2020.03.23
[백준 11048] 이동하기 (DFS, DP) (C/C++) (★)  (0) 2020.03.23
[백준 1890] 점프 (DFS, DP) (C/C++)  (0) 2020.03.22
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
 
string word;
int dp[2510][2510];
int minResult[2510];
 
int solve(int s, int e)
{
    if(s >= e)
    {
        return 1;
    }
    
    if(dp[s][e] != -1)
    {
        return dp[s][e];
    }
    
    dp[s][e] = 0;
    
    if(word[s] == word[e])
    {
        dp[s][e] = solve(s+1, e-1);
    }
    
    return dp[s][e];
}
 
int main(void)
{
//    freopen("B1509_input.txt", "r", stdin);
    
    cin >> word;
    word = "0" + word;
    
    memset(dp, -1, sizeof(dp));
    
    minResult[0] = 0;
    for(int i = 1; i < word.size(); i++)
    {
        minResult[i] = 99999999;
        
        for(int j = 1; j <= i; j++)
        {
            if(solve(j, i) == 1)
            {
                minResult[i] = min(minResult[i], minResult[j-1] + 1);
            }
        }
    }    
    
    cout << minResult[word.size()-1];
    
    return 0;
}
 cs
저작자표시

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

[백준 2157] 여행 (DP) (C/C++) (★★★)  (0) 2021.01.26
[백준 2167] 2차원 배열의 합 (DP) (C/C++) (★★)  (0) 2020.05.28
[백준 10942] 팰린드롬 ? (DP) (C/C++) (★★)  (0) 2020.03.23
[백준 11048] 이동하기 (DFS, DP) (C/C++) (★)  (0) 2020.03.23
[백준 1890] 점프 (DFS, DP) (C/C++)  (0) 2020.03.22

1.

#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
 
int N, M;
int arr[2010];
int dp[2010][2010]; // [시작][끝] 
 
int solve(int s, int e)
{
    if(s >= e)
    {
        return 1;
    }
    
    if(dp[s][e] != -1)
    {
        return dp[s][e];
    }
    
    dp[s][e] = 0;
    
    if(arr[s] == arr[e])
    {
        dp[s][e] = solve(s+1, e-1);    
    }
    
    return dp[s][e];
}
 
int main(void)
{
//    freopen("B10942_input.txt", "r", stdin);
    
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        cin >> arr[i];
    }
    memset(dp, -1, sizeof(dp));
    
    cin >> M;
    
    for(int i = 1; i <= M; i++)
    {
        int s, e;
        cin >> s >> e;
        
        cout << solve(s, e) << "\n";
    }
 
    return 0;
}
 cs

 

2.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int N, M;
int arr[2010];
int dp[2010][2010]; // [시작][끝] 
 
int main(void)
{
//    freopen("B10942_input.txt", "r", stdin);
    
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        cin >> arr[i];
    }
    
    // 길이 1
    for(int i = 1; i <= N; i++)
    {
        dp[i][i] = 1;    
    } 
    
    // 길이 2
    for(int i = 1; i <= N-1; i++)
    {
        if(arr[i] == arr[i+1])
        {
            dp[i][i+1] = 1;
        }    
    } 
    
    // 길이 3이상
    for(int k = 3; k <= N; k++)
    {
        for(int i = 1; i <= N-k+1; i++)
        {
            int j = i+k-1;
            
            if(arr[i] == arr[j] && dp[i+1][j-1] == 1)
            {
                dp[i][j] = 1;
            }
        }
    }
    
    cin >> M;
    
    for(int i = 1; i <= M; i++)
    {
        int s, e;
        cin >> s >> e;
        
        cout << dp[s][e] << "\n";
    }
 
    return 0;
}
 cs
저작자표시

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

[백준 2167] 2차원 배열의 합 (DP) (C/C++) (★★)  (0) 2020.05.28
[백준 1509] 팰린드롬 분할 (DP) (C/C++) (★★★)  (0) 2020.03.24
[백준 11048] 이동하기 (DFS, DP) (C/C++) (★)  (0) 2020.03.23
[백준 1890] 점프 (DFS, DP) (C/C++)  (0) 2020.03.22
[백준 9507] Generations of Tribbles (DP) (C/C++)  (0) 2020.03.22
#include <iostream>
#include <algorithm>
using namespace std;
 
int row, col;
int map[1010][1010];
int dp[1010][1010];
 
int dx[3] = {1, 0, 1}; 
int dy[3] = {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 map[x][y];
    }
    
    if(dp[x][y] != -1)
    {
        return dp[x][y];
    }
    
    for(int i = 0; i < 3; i++)
    {
        int xpos = x + dx[i];
        int ypos = y + dy[i];
            
        if(safe(xpos, ypos) == 1)
        {
            dp[x][y] = max(dp[x][y], DFS(xpos, ypos) + map[x][y]);
        }
    }
    
    return dp[x][y];
}
 
int main(void)
{
//    freopen("B11048_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' 카테고리의 다른 글

[백준 1509] 팰린드롬 분할 (DP) (C/C++) (★★★)  (0) 2020.03.24
[백준 10942] 팰린드롬 ? (DP) (C/C++) (★★)  (0) 2020.03.23
[백준 1890] 점프 (DFS, DP) (C/C++)  (0) 2020.03.22
[백준 9507] Generations of Tribbles (DP) (C/C++)  (0) 2020.03.22
[백준 1904] 타일 (DP) (C/C++)  (0) 2020.03.22
#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
int map[110][110];
long long dp[110][110];
 
int dx[2] = {0, 1}; // 우하
int dy[2] = {1, 0}; // 우하 
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < N && y < N)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
long long DFS(int x, int y)
{
    if(x == N-1 && y == N-1)
    {
        return 1;
    }
    else if(map[x][y] == 0)
    {
        return 0;
    }
    
    if(dp[x][y] != 0)
    {
        return dp[x][y];
    }
    
    for(int i = 0; i < 2; i++)
    {
        int xpos = x + (dx[i] * map[x][y]);
        int ypos = y + (dy[i] * map[x][y]);    
            
        if(safe(xpos, ypos) == 1)
        {
            dp[x][y] += DFS(xpos, ypos);
        }
    }
    
    return dp[x][y];
}
 
int main(void)
{
//    freopen("B1890_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            cin >> map[i][j];
        }
    }
    
    cout << DFS(0, 0);
    
    return 0;
}
cs
저작자표시

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

[백준 10942] 팰린드롬 ? (DP) (C/C++) (★★)  (0) 2020.03.23
[백준 11048] 이동하기 (DFS, DP) (C/C++) (★)  (0) 2020.03.23
[백준 9507] Generations of Tribbles (DP) (C/C++)  (0) 2020.03.22
[백준 1904] 타일 (DP) (C/C++)  (0) 2020.03.22
[백준 2096] 내려가기 (DP) (C/C++) (★★)  (0) 2020.03.22
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
int T, N;
long long dp[70];
 
long long solve(int n)
{
    if(dp[n] != 0)
    {
        return dp[n];
    }
    
    for(int i = n-1; i >= n-4; i--)
    {
        dp[n] += solve(i);    
    }
    
    return dp[n];
}
 
int main(void)
{
//    freopen("B9507_input.txt", "r", stdin);
 
    cin >> T;
    
    dp[0] = 1, dp[1] = 1, dp[2] = 2, dp[3] = 4;
    
    while(T--)
    {
        cin >> N;
        
        cout << solve(N) << endl;    
    }
    
    return 0;
}
cs
저작자표시

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

[백준 11048] 이동하기 (DFS, DP) (C/C++) (★)  (0) 2020.03.23
[백준 1890] 점프 (DFS, DP) (C/C++)  (0) 2020.03.22
[백준 1904] 타일 (DP) (C/C++)  (0) 2020.03.22
[백준 2096] 내려가기 (DP) (C/C++) (★★)  (0) 2020.03.22
[백준 1915] 가장 큰 정사각형 찾기 (DP) (C/C++) (★)  (0) 2020.03.17
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
int N;
int dp[1000010];
 
int solve(int n)
{
    if(n == 0)
    {
        return 1;
    }
    else if(n < 0)
    {
        return 0;
    }
    
    if(dp[n] != 0)
    {
        return dp[n];
    }
    
    dp[n] = solve(n-1) % 15746 + solve(n-2) % 15746;
    
    return dp[n] % 15746;
}
 
int main(void)
{
//    freopen("B1904_input.txt", "r", stdin);
 
    cin >> N;
    
    cout << solve(N);
    
    return 0;
}
cs
저작자표시

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

[백준 1890] 점프 (DFS, DP) (C/C++)  (0) 2020.03.22
[백준 9507] Generations of Tribbles (DP) (C/C++)  (0) 2020.03.22
[백준 2096] 내려가기 (DP) (C/C++) (★★)  (0) 2020.03.22
[백준 1915] 가장 큰 정사각형 찾기 (DP) (C/C++) (★)  (0) 2020.03.17
[백준 11051] 이항 계수 2 (DP) (C/C++)  (0) 2020.03.17

+ Recent posts

티스토리툴바