[C++] Dynamic Programming을 알아보자.

DP

Dynamic Programming

동적 프로그래밍

알고리즘 문제에서 많이 출제되며

아주 쉬운 난이도부터 아주 어려운 난이도까지 다양하게 산재

기초

점화식 도출

어떤 조건에서 완료할 것인지

어떤 예외 처리가 필요한지

에 대해 기본적으로 익히고 응용으로

----------

응용

실전 문제에서 이 문제가 DP로 해결되는지 모델링되는지 판단하는 것 -> 사실 DP로 풀 수 있는지 없는지 판단하는 것도 실력

(어떤 자료구조를 사용해서 이 정보로 다음 정보를 얻을 수 있고, 결과를 얻을 수 있는데.. 등)

DP이면서 여러 다른 알고리즘들을 사용해야 하는 문제 등

..

주저리주저리 썼지만 

진짜 이건 다 개소리 맞는듯.

나중에 종만북에서 등장하는 알고리즘

---

개념?

현재 상태를 통해 다음 상태를 안다

-> 이전 정보를 통해 현재 정보를 안다.

간단한 예제를 들어 피보나치 수열을 구한다고 하자.

아래 소스 코드를 보면..

#include<bits/stdc++.h>
int N;
long long a[91]={0,1};
int main(){
    scanf("%d",&N);
    for(int i=2;i<N+1;i++){a[i]=a[i-1]+a[i-2];}
    printf("%lld",a[N]);
}

현재 (i번 째) 피보나치 수열을 알고 싶을 때 이전 수열 값(i-1, i-2)번 째 값을 사용한다.

점화식은? a_i = a_(i-1)+ a_(i-2)

어떤 조건에서 완료? i==n

어떤 예외 처리? 딱히 없음..

이게 전부입니다. 

쉽죠

아뇨 어렵습니다.

다른 문제를 볼까요?

동전

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. (각각의 동전은 몇 개라도 사용할 수 있다.)

이문제는 백준 온라인저지의 "동전1" 이라는 문제입니다.

이제 생각해보자

아.. 문제 접근법에 대한 포스팅도 해야될거같다.

너무 막나간 느낌이랄까

일단. 그럼. 이 문제를 풀기 위해 모델링을 해보자.

힌트는 단 하나 DP로 풀린다.

각자 먼저 생각해보길

---

답은 여러 방법으로 나올 수 있겠지만

내가 푼 방법은 돈 액수 자체를 하나의 상태(인덱스)로 보고, 만들 수 있는 방법의 수를 value로 넣었다. 

즉 a[idx]안에 담긴 value는 idx원을 만드는 방법의 갯수 이다.

예를 들어 보자.

1원 2원 5원 짜리 동전이 있고

10원을 만드는 방법의 수를 물어봤을 때

배열의 값들은 어떻게 될까?

a[0] = 0 --- 없음

a[1] = 1 --- (1*1 + 2*0 + 5*0)

a[2] = 2 --- (1*2 + 2*0 + 5*0) / (1*0 + 2*1 + 5*0)

a[3] = 2 --- (1*3 + 2*0 + 5*0) / (1*1 + 2*1 + 5*0)

a[4] = 3 --- (1*4 + 2*0 + 5*0) / (1*2 + 2*1 + 5*0) / (1*0 + 2*2 + 5*0)

a[5] = 4 --- (1*5 + 2*0 + 5*0) / (1*3 + 2*1 + 5*0) / (1*1 + 2*2 + 5*0) / (1*0 + 2*0 + 5*1)

생각해보자 무엇이 보이는가?

a[0] = 0

a[1] = (a[0] + 1원)

a[2] = (a[1] + 1원) / (a[0] + 2원)

a[3] = (a[2] + 1원) / (a[1] + 2원)

a[4] = (a[3] + 1원) / (a[2] + 2원)

a[5] = (a[4] + 1원) / (a[3] + 2원) / (a[0] + 5원)

점화식이 보이는가?

a[5] ----- 5원을 만들 수 있는 방법의 수는

a[4] + a[3] + a[0] 이다.

왜? 4원을 만들 수 있는 방법의 수(1원 더하면됨) + 3원을 만들 수 있는 방법의 수(2원 더하면됨) + 0원을 만들 수 있는 방법의 수(5원 더하면됨)

여기서 의문점은.. 만약 3원을 만들 수 있는 방법의 수에서 1원을 2번 더하면 안되냐?

-> 3원을 만들 수 있는 방법의 수에서 1원을 2번 더하는 행위는 4원을 만들 수 있는 방법의 수에서 1원을 더하는 것에 포함된다.

즉, 중복 포함되어 버린다.

이해가 안 간다면 계속 곱씹어서 생각하길 빈다.

진짜 쉬운 문제다.

이해했다면 위 문제 링크를 따라 문제를 풀어보도록 해라.

아래는 정답

#include<bits/stdc++.h>
using namespace std;
int n,k,i,j,c,dp[10001]={1,};
int main(){
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;++i){
        scanf("%d",&c);
        for(int j=0;j<=k-c;++j)
            dp[j+c]+=dp[j];
    }
    printf("%d",dp[k]);
}