dp 연습

탑다운과 바텀업 두가지가 대표적인 풀이이며, 설계를 하고 풀어야 수월함.

 

#include <iostream>
using namespace std;
int map[6][3] = {
    0, 0, 0,
    3, 5, -1,
    9, -1, 1,
    10, 5, 20,
    -1, 5, 6,
    15, 1, 5
}, cal[6][3], direct[3][2] = {1, -1, 1, 0, 1, 1};
int main()
{
    for(int i=0; i<3; i++)
        cal[5][i] = map[5][i];
    for(int i=4; i>=0; i--)
    {
        for(int j=0; j<3; j++)
        {
            if(map[i][j] == -1) continue;
            for(int k=0; k<3; k++)
            {
                int dy = direct[k][0] + i;
                int dx = direct[k][1] + j;
                if(dx > 2 || dx < 0) continue;
                if(map[dy][dx] == -1) continue;
                if(cal[i][j] < cal[dy][dx] + map[i][j])
                    cal[i][j] = cal[dy][dx] + map[i][j];
            }
        }
    }
        
    for(int i=0; i<3; i++)
    {
    
        cout << cal[0][i] << ' ';
    }
    
    return 0;
}

 

최소 동전 갯수 구하기

#include <iostream>
#include <algorithm>
using namespace std;
int coin, num[3] = {10, 50, 70};
int getCnt(int cost)
{
    if(cost < 0)
        return 1e9;
    if(cost == 0)
        return 0;
    
    int cnt = 1e9;
    for(int i=0; i<3; i++)
    {
        cnt = min(cnt, getCnt(cost - num[i]) + 1);
    }
    
    return cnt;
}
int main()
{
    cin >> coin;
    cout << getCnt(coin);
    
    return 0;
}

 

메모이제이션 : 이미 구한 값을 재사용하는 것

피보나치 수열을 구하는 것이 메모이제이션을 적용할 수 있는 가장 쉬운 경우이다.

#include <iostream>
using namespace std;
long long num[100000];

long long fibo(int n)
{
    if(num[n] != 0) return num[n];
    if(n == 0) return 0;
    if(n == 1) return  1;
    
    return num[n] = fibo(n-1) + fibo(n-2);
}
int main()
{
    num[1] = 1;
    cout << fibo(20);
    return 0;
}

 

 

문제에 따라 바텀업, 탑다운 방식의 차이가 있음.

문제마다 어떤 것으로 풀 지 정하는 것은 자신의 감 즉, 많이 풀수록 느낌이 온다.

 

탑다운의 경우 반복되는 동작이 매우 많기 때문에 메모이제이션을 사용해야 바텀업과 동일한 성능이 나온다.

메모이제이션을 사용하여 동전 최소 갯수 구하기

 

#include <iostream>
using namespace std;
int coin, num[100000], money[4] ={10, 50, 70, 100};

int getMinCnt(int cost)
{
    if(cost < 0)
        return 1e9;
    if(cost == 0)
        return 0;
    if(num[cost] != 1e9)
        return num[cost];
    
    for(int i=0; i<4; i++)
    {
        num[cost] = min(num[cost], getMinCnt(cost - money[i]) + 1);
    }
    
    return num[cost];
}
int main()
{
    cin >> coin;
    fill(num, num+100000, 1e9);
    cout << getMinCnt(coin);
    return 0;
}