[BOJ 2293] 동전 1

나는 왜 이문제를 못풀었을까?

dp문제를 풀때 규칙이 바로 보이지 않으면 손을 놓고 머리속으로만 풀려고 하는 안좋은 습관이 있다.

규칙이 보이지 않으면 손을 부지런히 움직여서 규칙이 보일때까지 시행착오를 겪으면서 발견해야하는데 발견하지 못할것 같다는 두려움과 손을 놀려야 한다는 귀찮음 때문인것 같다. 그렇다고 머릿속으로만 생각하면 난 천재처럼 머리속에 화이트보드가 있는것도 아니니 초 스피드로 사라지는 휘발성 메모리를 가지고 dp 문제를 풀라고하니 가당치가 않았던 것이다.

고등학교 수열과 마찬가지로 dp는 무조건 규칙 찾기이고 그때 당시 '자기 손으로 지저분하게라도 직접 풀어내는것이 베스트'라는 어떤 수학강사의 말이 다시금 떠올랐다.

다시한번 상기하자 dp는 수열이고 수열의 핵심은 규칙찾기고 노다가를 해서라도 규칙을 내손으로 직접 찾는 버릇을 들여야한다.

 

d[n]을 현재까지 가지고 있는 동전들을 가지고 n을 만드는 방법의 수라고 테이블을 정의 했을때

먼저 규칙을 찾기위해 문제를 단순하게 만들어서 생각해보자

1원짜리 동전만 있을때와 1,2원 짜리 동전만 있을때 1,2,5원짜리 동전만 있을때로 점차 확장되게 생각하면서

직접 d[n]이 어떻게 달라지는지 확인해보면

동전의 개수가 늘어날때마다

d[i] = d[i] + d[ i - 새로운 동전값 ] 으로 갱신되는것을 알수 있다.

직접 손으로 쓰면서 테이블을 채우다보면 증명할 필요없이 수학적인 직관적으로 그렇게 될수밖에 없다고 깨닫게 된다.

그 수학적 직관은 새로운 동전을 쓰는 상황에서 이미 확정적으로 그 동전을 추가했기 때문에 점화식이 저렇게 도출되는것까지 확신이 드는것이다. 이처럼 처음에는 규칙이 안보여도 막상하다보면 규칙을 발견하고 직관으로 확인까지 되는경우가 있으니

dp문제는 규칙을 발견못해도 좋으니 반드시 손으로 풀것을 명심하자.

 

코드는 아래와 같다.

#include <bits/stdc++.h>
using namespace std;

int d[10005];
int a[105];

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    int k;
    cin >> n >> k;
    for(int i=1; i<=n; i++) cin >> a[i];

    d[0] = 1;
    for(int j=1; j<=n; j++)
        for(int i=1; i<=k; i++) if(i - a[j] >= 0) d[i] = d[i] + d[i-a[j]];

    cout << d[k] << '\n';


}