5. 1차원, 2차원 dp

5.md

0.01MB

DP = 디피 = 다이나믹 프로그래밍 = Dynamic Programming

문제를 쪼개서 해결하는 방법의 한 분류.

주어진 초기값을 바탕으로 순차적으로 값을 메모를 해가면서 구한다.

1. 1차원 dp

(1)피보나치 수

그냥 재귀적으로 해결하면 O(2^N)이 걸리지만, DP를 사용하면 O(N)이 걸린다.

다음은 for문을 이용한 dp

#include <iostream>
using namespace std;
int dp[100];
int main(){
    int N; cin >> N;

    dp[0]=0;
    dp[1]=1; // 초기값 설정

    for(int i=2; i<=N; ++i){
        dp[i]=dp[i-1]+dp[i-2]; // 점화식을 여기에 활용
    }
    cout << dp[N] << '\n';
}

다음은 재귀를 이용한 dp

#include <iostream>
#include <algorithm>
using namespace std;
const long long NOT_YET = -1;
long long dp[91];
long long solve(int N){
    if(dp[N] != NOT_YET) return dp[N];
    return dp[N] = solve(N-1) + solve(N-2);
}
int main(){
    int N; cin >> N;
    fill(dp, dp + N + 1, NOT_YET); // memset이랑 같음.
    dp[0] = 0;
    dp[1] = 1;

    cout << solve(N) << '\n';
}

참고 문제 : boj.kr/2747, boj.kr/2748

(2) 최적의 해 찾아가기

최적의 해를 한번 찾았다면, 앞으로는 그 최적의 해와 동일한 조건일 때 그 값을 쓴다.

최적의 해를 찾지 못했다면, 문제를 쪼개서 최적의 해를 찾는다.

살짝 추상적인 말이긴 한데, 1463번의 코드를 보면서 해보자.

#include <iostream>
#include <algorithm>
using namespace std;
int dp[1000001];
//dp[i]=i에서 1로 만드는 최소 횟수
int solve(int N){
    if(dp[N]!=-1) return dp[N];
    if(N%3==0 && N%2==0) return dp[N]=min(min(f(N/3)+1, f(N/2)+1), f(N-1)+1);
    if(N%3==0) return dp[N]=min(f(N/3)+1, f(N-1)+1);
    if(N%2==0) return dp[N]=min(f(N/2)+1, f(N-1)+1);
    return dp[N]=f(N-1)+1;
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int X; cin >> X;
    fill(dp, dp+X+2, -1);
    dp[0]=0;
    dp[1]=0;
    cout << solve(X) << '\n';
}

dp[i]=i에서 1로 만드는 최소 횟수다.

solve라는 함수에서,

​ N이 6의 배수일 때, 3으로 나눌 수 있고, 2로 나눌 수 있고 -1을 할 수도 있다. 이중 최솟값이 dp[i]가 된다.

​ N이 3의 배수일 때, 3으로 나눌 수 있고, -1을 할 수도 있다. 이중 최솟값이 dp[i]가 된다.

​ N이 2의 배수일 때, 2로 나눌 수 있고, -1을 할 수도 있다. 이중 최솟값이 dp[i]가 된다.

​ 위의 모든 조건이 아닐 때, -1을 한 값이 dp[i]이다.

즉, 점화식은 dp[i]=min(dp[i-1], dp[i/2], dp[i/3]) + 1

아래와 같이 solve 함수를 구성할 수도 있다.

int solve(int X) {
    if (X == 1)
        return 0;
    if (dp[X] != 0)
        return dp[X];
    dp[X] = solve(X-1);
    if (X % 2 == 0)
        dp[X] = min(dp[X], solve(X/2));
    if (X % 3 == 0)
        dp[X] = min(dp[X], solve(X/3));
    dp[X]++;
    return dp[X];
}

참고 문제 : boj.kr/1463

2. 이차원 dp

boj.kr/1149번을 보자.

1차원 dp로 하면 굉장히 까다롭다. 이때, 이차원dp를 쓴다.

dp[N][col] : N번째 집을 col로 칠했을 때 지금까지의 최소비용

dp[N][R] = min(dp[N-1][G], dp[N-1][B])+cost[N]

참고 문제 : boj.kr/1149

3. dp 문제들

dp는 다른 알고리즘보다 문제를 많이 풀어보는걸 추천한다.

다양한 유형이 있고, 머리로 생각해보고, 손으로 직접 풀어봐야 답이 보이는 경우도 많다.

참고 문제 : boj.kr/11726, boj.kr/11727, boj.kr/2579, boj.kr/2193, boj.kr/2156, boj.kr/11050, boj.kr/11051

99. 부록 : 참고 문제 풀이

• boj.kr/2747

#include <iostream>
using namespace std;
int dp[100];
int main(){
    int N; cin >> N;

    dp[0]=0;
    dp[1]=1; // 초기값 설정

    for(int i=2; i<=N; ++i){
        dp[i]=dp[i-1]+dp[i-2]; // 점화식을 여기에 활용
    }
    cout << dp[N] << '\n';
}

• boj.kr/2748

#include <iostream>
using namespace std;
long long int dp[100];
int main(){
    int N; cin >> N;

    dp[0]=0;
    dp[1]=1; // 초기값 설정

    for(int i=2; i<=N; ++i){
        dp[i]=dp[i-1]+dp[i-2]; // 점화식을 여기에 활용
    }
    cout << dp[N] << '\n';
}

• boj.kr/1463

#include <iostream>
#include <algorithm>
using namespace std;
int dp[1000001];
//dp[i]=i에서 1로 만드는 최소 횟수
int f(int N){
    if(dp[N]!=-1) return dp[N];
    if(N%3==0 && N%2==0) return dp[N]=min(min(f(N/3)+1, f(N/2)+1), f(N-1)+1);
    if(N%3==0) return dp[N]=min(f(N/3)+1, f(N-1)+1);
    if(N%2==0) return dp[N]=min(f(N/2)+1, f(N-1)+1);
    return dp[N]=f(N-1)+1;
}
int solve(int X) {
    if (X == 1)
        return 0;
    if (dp[X] != 0)
        return dp[X];
    dp[X] = solve(X-1);
    if (X % 2 == 0)
        dp[X] = min(dp[X], solve(X/2));
    if (X % 3 == 0)
        dp[X] = min(dp[X], solve(X/3));
    dp[X]++;
    return dp[X];
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int N; cin >> N;
    fill(dp, dp+N+2, -1);
    dp[0]=0;
    dp[1]=0;
    cout << f(N) << '\n';
}

• boj.kr/1149

#include <iostream>
using namespace std;
int cost[1000][3];
int dp[1000][3];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int N;  cin>>N;
    for(int i=0; i<N; ++i){
        for(int j=0; j<3; ++j){
            cin >> cost[i][j];
        }
    }

    dp[0][0]=cost[0][0];
    dp[0][1]=cost[0][1];
    dp[0][2]=cost[0][2];

    for(int i=1; i<N; ++i){
        for(int c=0; c<3; ++c){
            dp[i][c] = 1e9; // 큰 값으로 초기화
            for(int prvc = 0; prvc<3; ++prvc){
                if(c==prvc) continue;
                dp[i][c]=min(dp[i][c], dp[i-1][prvc] + cost[i][c]);
            }
        }
    }
    cout << min(dp[N-1][0], min(dp[N-1][1], dp[N-1][2])) << '\n';
}

• boj.kr/11726

#include <iostream>
#include <algorithm>
#define D 10007
using namespace std;
int dp[10000];
int solve(int x){
    if(x==0) return 0;
    if(dp[x]) return dp[x];
    return dp[x]=(solve(x-2)%D + solve(x-1)%D)%D;
}
int main(){
    int n;  cin >> n;
    dp[1]=1;
    dp[2]=2;
    cout << solve(n) << '\n';
}

• boj.kr/11727

#include <iostream>
#include <algorithm>
#define D 10007
using namespace std;
int dp[10000];
int solve(int x){
    if(x==0) return 0;
    if(dp[x]) return dp[x];
    return dp[x]=((solve(x-2)*2)%D + solve(x-1)%D)%D;
}
int main(){
    int n;  cin >> n;
    dp[1]=1;
    dp[2]=3;
    cout << solve(n) << '\n';
}

• boj.kr/2579

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long int ll;
ll cost[303];
ll dp[303][3];
//dp[i][1] : i칸을 1칸 연속으로 밟았을 때
//dp[i][2] : i칸을 2칸 연속으로 밟았을 때 

ll N;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N;
    for(int i=1; i<=N; ++i){
        cin >> cost[i];
    }
    dp[1][1] = cost[1];
    dp[2][1] = cost[2];
    dp[2][2] = cost[1]+cost[2];
    for(int i=3; i<=N; ++i){
        dp[i][1] = max(dp[i-2][1],dp[i-2][2]) + cost[i];
        dp[i][2] = dp[i-1][1] + cost[i];
    }
    cout << max(dp[N][1], dp[N][2]) << '\n';

}

• boj.kr/2193

#include <iostream>
using namespace std;
typedef long long ll;
ll dp[100][2]; // [0] : 0으로 끝나는거, [1] : 1로 끝나는거
int main(){
    int N;  cin >> N;
    dp[1][0] = 0;
    dp[1][1] = 1;
    dp[2][0] = 1;
    dp[2][1] = 0;
    for(int i=2; i<=N; ++i){
        dp[i][0] = dp[i-1][0] + dp[i-1][1];
        dp[i][1] = dp[i-1][0];
    }
    cout << dp[N][0] + dp[N][1] << '\n';
}

• boj.kr/2156

#include <iostream>
using namespace std;
typedef long long int ll;
ll cost[100001];
ll dp[100001][3];
//[0] : 연속으로 0개
//[1] : 연속으로 1개
//[2] : 연속으로 2개


int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll n;
    cin >> n;
    for(int i=1; i<=n; ++i){
        cin >> cost[i];
    }
    dp[1][0] = 0;
    dp[1][1] = cost[1];
    dp[2][0] = cost[1];
    dp[2][1] = cost[2];
    dp[2][2] = cost[1] + cost[2];
    for(int i=3; i<=n; ++i){
        dp[i][0] = max(dp[i-1][0], max(dp[i-1][1], dp[i-1][2]));
        dp[i][1] = dp[i-1][0] + cost[i];
        dp[i][2] = dp[i-1][1] + cost[i];
    }
    cout << max(dp[n][1], max(dp[n][2], dp[n][0])) << '\n';
}

• boj.kr/11050

#include <iostream>
using namespace std;
typedef long long int ll;
ll fact[100];
int main(){
    ll N, K;   cin >> N >> K;
    fact[0]=1;
    fact[1]=1;
    for(ll i=2; i<=N; ++i){
        fact[i]=fact[i-1]*i;
    }
    cout << fact[N] / (fact[K] * fact[N-K]) << '\n';
}

• boj.kr/11051

#include <iostream>
#define D 10007
using namespace std;
typedef long long int ll;
ll pas_tri[1002][1002]; // 파스칼의 삼각형
int main(){
    ll N, K;   cin >> N >> K;
    for(int i=1; i<=N+1; ++i){
        for(int j=1; j<=i; ++j){
            if(j==1 || j==i) pas_tri[i][j]=1;
            else pas_tri[i][j] = (pas_tri[i-1][j-1]%D + pas_tri[i-1][j]%D)%D;
        }
    }
    cout << pas_tri[N+1][K+1] << '\n';
}
/*
a[n][1] = 1
a[n][n] = 1
a[n][k] = a[n-1][k-1] + a[n-1][k]

nCk = n-1Ck-1 + n-1Ck
*/