#include <iostream>
#include <string>
#include <algorithm>
#include <string.h>
using namespace std;
 
int cost[1010][1010];
int dp[1010][1010][4]; // 0 : 왼쪽, 1 : 중앙, 2 : 오른쪽 
int row, col;
 
int solve(int x, int y, int dir)
{
    if(x == row)
    {
        return 0;
    }
    
    if(dp[x][y][dir] != 99999999)
    {
        return dp[x][y][dir];
    }
    
    // 왼쪽
    if(dir != 0 && y-1 >= 0)
    {
        dp[x][y][dir] = solve(x+1, y-1, 0) + cost[x][y];     
    } 
    
    // 중앙 
    if(dir != 1)
    {
        dp[x][y][dir] = min(dp[x][y][dir], solve(x+1, y, 1) + cost[x][y]);    
    }
    
    // 오른쪽
    if(dir != 2 && y+1 < col)
    {
        dp[x][y][dir] = min(dp[x][y][dir], solve(x+1, y+1, 2) + cost[x][y]); 
    } 
    
    return dp[x][y][dir];
}
 
int main(void)
{
//    freopen("B17485_input.txt", "r", stdin);
    
    cin >> row >> col;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> cost[i][j];
            
            for(int k = 0; k < 4; k++)
            {
                dp[i][j][k] = 99999999;    
            }
        }
    }
     
    int Min = 99999999;
    for(int i = 0; i < col; i++)
    {
        // 처음에는 방향이 없기 때문에 dir에 3을 대입 
        Min = min(Min, solve(0, i, 3));
    }
    
    cout << Min;
    
    return 0;
}
cs
저작자표시

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

[백준 1003] 피보나치 함수 (DP) (C/C++)  (0) 2020.03.15
[백준 10211] Maximum Subarray (DP) (C/C++) (★★)  (0) 2020.03.15
[백준 12865] 평범한 배낭 (DP) (C/C++) (★)  (0) 2020.03.13
[백준 1480] 보석 모으기 (DP, Bitmask) (C/C++) (★★★)  (0) 2020.03.13
[백준 2098] 외판원 순회 (DP, Bitmask) (C/C++) (★★★)  (0) 2020.03.12
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
int N, K;
int dp[101][100001];
int w[101];
int v[101];
 
int solve(int item, int capacity)
{
    if(item >= N)
    {
        return 0;
    }
    
    if(dp[item][capacity] != 0)
    {
        return dp[item][capacity];
    }
    
    // 배낭에 넣지 않는 경우 
    dp[item][capacity] = solve(item+1, capacity);     
    
    // 배낭에 넣는 경우 
    if(capacity-w[item] >= 0)
    {
        dp[item][capacity] = max(dp[item][capacity], solve(item+1, capacity-w[item]) + v[item]);    
    } 
    
    return dp[item][capacity]; 
}
 
int main(void)
{
//    freopen("B12865_input.txt", "r", stdin);
    
    cin >> N >> K;
    
    for(int i = 0; i < N; i++)
    {
        cin >> w[i] >> v[i];    
    }
    
    cout << solve(0, K);
    
    return 0;
}
cs
저작자표시

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

[백준 10211] Maximum Subarray (DP) (C/C++) (★★)  (0) 2020.03.15
[백준 17485] 진우의 달 여행 (DP) (C/C++) (★)  (0) 2020.03.13
[백준 1480] 보석 모으기 (DP, Bitmask) (C/C++) (★★★)  (0) 2020.03.13
[백준 2098] 외판원 순회 (DP, Bitmask) (C/C++) (★★★)  (0) 2020.03.12
[백준 2294] 동전 2 (DP) (C/C++) (★★)  (0) 2020.03.07
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
int N, M, C;
int jewel[15]; 
int dp[12][1<<13][22]; // [현재가방][챙긴보석][남은한도] 
 
int solve(int cur, int visited, int capacity)
{
    if(cur == M)
    {
        return 0;
    }
    
    if(dp[cur][visited][capacity] != 0)
    {
        return dp[cur][visited][capacity];
    } 
    
    for(int i = 0; i < N; i++)
    {
        if(visited & (1 << i))
        {
            continue;
        }    
        
        if(capacity < jewel[i])
        {
            dp[cur][visited][capacity] = max(dp[cur][visited][capacity], solve(cur+1, visited, C));    
        }
        else 
        {
            dp[cur][visited][capacity] = max(dp[cur][visited][capacity], solve(cur, visited | (1 << i), capacity - jewel[i]) + 1);
        }
    } 
    
    return dp[cur][visited][capacity];
}
 
int main(void)
{
//    freopen("B1480_input.txt", "r", stdin);
    
    cin >> N >> M >> C;
    
    for(int i = 0; i < N; i++)
    {
        cin >> jewel[i];
    }
    
    cout << solve(0, 0, C);
    
    return 0;
}
cs
저작자표시

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

[백준 17485] 진우의 달 여행 (DP) (C/C++) (★)  (0) 2020.03.13
[백준 12865] 평범한 배낭 (DP) (C/C++) (★)  (0) 2020.03.13
[백준 2098] 외판원 순회 (DP, Bitmask) (C/C++) (★★★)  (0) 2020.03.12
[백준 2294] 동전 2 (DP) (C/C++) (★★)  (0) 2020.03.07
[백준 2293] 동전 1 (DP) (C/C++) (★★)  (0) 2020.03.07
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
int dist[20][20];
int dp[20][1<<16]; // [현재도시][방문한도시]
int N;
 
int solve(int cur, int visited)
{
    // 모든 마을 방문시 
    if(visited == (1 << N) - 1)
    {
        // 0번 마을로 다시 돌아갈 수 있을때 
        if(dist[cur][0] != 0)
        {
            return dist[cur][0];
        }
        // 그 코스는 불가능 하도록 만들기 위해 매우 큰 수를 return
        else
        {
            return 99999999;    
        }
    }
    
    if(dp[cur][visited] != -1)
    {
        return dp[cur][visited];
    } 
    
    dp[cur][visited] = 99999999;
    
    for(int i = 1; i < N; i++)
    {
        // i번째 지역을 방문한 경우 
        if(visited & (1 << i))
        {
            continue;
        }    
        
        // 해당 지역의 비용이 0인 경우 
        if(dist[cur][i] == 0)
        {
            continue;
        }
        
        dp[cur][visited] = min(dp[cur][visited], solve(i, visited | (1 << i)) + dist[cur][i]);
    } 
    
    return dp[cur][visited];
}
 
int main(void)
{
//    freopen("B2098_input.txt", "r", stdin);
    
    cin >> N; 
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            cin >> dist[i][j];    
        }
    }
    
    memset(dp, -1, sizeof(dp));
    
    // 0 →1 →2 →3 →4 →0  시작점이 0인 최소비용 루트가 있다고 가정해보자. 이 때 'A원'의 비용이 들었다면, 
    // 2 →3 →4 →0 →1 →2  시작점이 2인 최소비용 루트는 시작점과 관계없이 'A원'의 비용이 든다. 
    cout << solve(0, 1);
    
    return 0;
}
cs
저작자표시

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

[백준 12865] 평범한 배낭 (DP) (C/C++) (★)  (0) 2020.03.13
[백준 1480] 보석 모으기 (DP, Bitmask) (C/C++) (★★★)  (0) 2020.03.13
[백준 2294] 동전 2 (DP) (C/C++) (★★)  (0) 2020.03.07
[백준 2293] 동전 1 (DP) (C/C++) (★★)  (0) 2020.03.07
[백준 11052] 카드 구매하기 (DP) (C/C++)  (0) 2020.01.22
#include <iostream>
#include <algorithm>
using namespace std;
 
int main(void)
{
//    freopen("B2294_input.txt", "r", stdin);
    
    int n, k;
    int dp[10010] = {0};
    int coin[10010];
    
    cin >> n >> k;
    
    for(int i = 0; i < n; i++)
    {
        cin >> coin[i]; 
    }
    
    for(int i = 0; i <= k; i++)
    {
        dp[i] = 99999999;
    }
    dp[0] = 0;
    
    for(int i = 0; i < n; i++)
    {
        for(int j = coin[i]; j <= k; j++)
        {
            dp[j] = min(dp[j], dp[j-coin[i]] + 1);
        }
    }
    
    if(dp[k] == 99999999)
    {
        cout << "-1";
    }
    else
    {
        cout << dp[k];    
    }
    
    return 0;
}
cs
저작자표시

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

[백준 1480] 보석 모으기 (DP, Bitmask) (C/C++) (★★★)  (0) 2020.03.13
[백준 2098] 외판원 순회 (DP, Bitmask) (C/C++) (★★★)  (0) 2020.03.12
[백준 2293] 동전 1 (DP) (C/C++) (★★)  (0) 2020.03.07
[백준 11052] 카드 구매하기 (DP) (C/C++)  (0) 2020.01.22
[백준 2011] 암호코드 (DP) (C/C++) (★)  (0) 2020.01.22
#include <iostream>
#include <algorithm>
using namespace std;
 
int main(void)
{
//    freopen("B2293_input.txt", "r", stdin);
    
    int n, k;
    long long dp[10010] = {0};
    int coin[10010];
        
    cin >> n >> k;
    
    for(int i = 0; i < n; i++)
    {
        cin >> coin[i];
    }
 
    dp[0] = 1;
    
    for(int i = 0; i < n; i++)
    {
        for(int j = coin[i]; j <= k; j++)
        {
            dp[j] = dp[j] + dp[j-coin[i]];
        }
    }
    
    cout << dp[k];
    
    return 0;
}
cs
저작자표시

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

[백준 2098] 외판원 순회 (DP, Bitmask) (C/C++) (★★★)  (0) 2020.03.12
[백준 2294] 동전 2 (DP) (C/C++) (★★)  (0) 2020.03.07
[백준 11052] 카드 구매하기 (DP) (C/C++)  (0) 2020.01.22
[백준 2011] 암호코드 (DP) (C/C++) (★)  (0) 2020.01.22
[백준 9461] 파도반 수열(DP) (C/C++)  (0) 2020.01.22
#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
long long card[1010];
long long dp[1010];
 
long long solve(int cnt)
{
    if(dp[cnt] != 0)
    {
        return dp[cnt];
    }
 
    for(int i = 1; i <= N; i++)
    {
        if(cnt+i <= N)
        {
            dp[cnt] = max(dp[cnt], solve(cnt+i) + card[i]);    
        }
    }
    
    return dp[cnt];
}
 
int main(void)
{
//    freopen("B11052_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        cin >> card[i];
    }
    
    cout << solve(0);
    
    return 0;
}
cs
저작자표시

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

[백준 2294] 동전 2 (DP) (C/C++) (★★)  (0) 2020.03.07
[백준 2293] 동전 1 (DP) (C/C++) (★★)  (0) 2020.03.07
[백준 2011] 암호코드 (DP) (C/C++) (★)  (0) 2020.01.22
[백준 9461] 파도반 수열(DP) (C/C++)  (0) 2020.01.22
[백준 2225] 합분해 (DP) (C/C++)  (0) 2020.01.22
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
 
#define MOD 1000000
 
string N;
long long dp[5010];
 
long long solve(int idx)
{
    if(idx >= N.size())
    {
        return 0;
    }
    else if(idx == N.size()-1)
    {
        return 1;
    }
    
    if(dp[idx] != 0)
    {
        return dp[idx];
    }
    
    if('1' <= N[idx+1])
    {
        dp[idx] = solve(idx+1) % MOD;    
    }
    
    if((N[idx+1] == '1') || (N[idx+1] == '2' && N[idx+2] <= '6'))
    {
        dp[idx] = (dp[idx] + solve(idx+2)) % MOD;    
    }
    
    return dp[idx];
}
 
int main(void)
{
//    freopen("B2011_input.txt", "r", stdin);
    
    cin >> N; 
    
    N = "0" + N;
    
    cout << solve(0);
    
    return 0;
}
cs
저작자표시

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

[백준 2293] 동전 1 (DP) (C/C++) (★★)  (0) 2020.03.07
[백준 11052] 카드 구매하기 (DP) (C/C++)  (0) 2020.01.22
[백준 9461] 파도반 수열(DP) (C/C++)  (0) 2020.01.22
[백준 2225] 합분해 (DP) (C/C++)  (0) 2020.01.22
[백준 2133] 타일 채우기 (DP) (C/C++) (★★★)  (0) 2020.01.21

+ Recent posts

티스토리툴바