[백준/Baekjoon] 2293 동전 1 C++ :: Dynamic Programming

https://www.acmicpc.net/problem/2293

2293번: 동전 1

---

1. Logic

- 처음에 구현한 방식은 DP테이블을 세우고 재귀함수로 문제를 풀었었다.

동전의 sum 값과 얼마짜리 동전을 사용했는지를 표기하는 DP테이블을 구성했고 dp[10001][101]로 구성했다 이렇게 되면 n * k만 해도 4MB가 넘어가므로 당연하게도 메모리초과가 났다.

 

이 다음 생각한 방법으로는 상향식으로 흔히 점화식을 세워서 푸는 방법으로 풀었다.

 

항상 재귀로 풀으려고해서 점화식을 세우는 방법은 어려워서 다른 사람의 솔루션을 참고했다.

다른 사람의 코드를 보고 내가 이해한 방법을 설명하겠다.

 

{1, 2, 3}으로 설명을 할 것인데

 

먼저 1원짜리 동전을 사용할 경우 동전의 갯수가 상관이 없기 때문에 1~10까지 만들 수 있는 방법은 각 1개씩이다.

다음 2원짜리 동전을 사용할 경우 2원짜리 동전은 당연하게도 1원을 만들 수 없기때문에 2원부터 시작한다.

반면 1원짜리 동전으로는 2원을 만들 수 있기 때문에 1원으로 만들수 있는 경우의 수 + 현재 2원으로 만들 수 있는 경우의 수 를 더해준다

dp[3] = dp[3] + dp[3 - vec[0]] => dp3 = dp[3] + dp[2]

 

dp[3] += dp[0]인 경우는  3원짜리를 사용할때 0원을 가진상태에서 3원짜리 한개를 만들 수 있는 경우의 수 1

dp[3] += dp[1]인 경우 1원짜리를 3개 사용해서 만들 수 있는 경우의 수 1개

dp[3] += d[[2]인 경우 dp[2]는 2원이 있는 상태에서 3원을 만들 수 있는 경우의수 (2원 1개 + 1원 1개)

하지만 dp[2]의 값에 dp[1]이 포함되어있기 때문에 최종적으로 새로운 경우의 수 인 3원짜리로 만들 수 있는 경우의수와 나머지 1원과 2원으로 만들 수 있느 ㄴ경우의 수인 dp[2]를 더해준다.

 

최종적으로 식은 dp[j]= dp[j  + dp[j = coinValue[i]];

i : 입력받은 돈의 가치의 인덱스

j : 선택한 돈의 가치부터 그 이후 구하고싶은 액수까지의 범위 

 

---

2. Code

처음에 재귀로 푼 코드 > 메모리 초과

#include<bits/stdc++.h>

using namespace std;

int n, k;

vector<int> vec;
int dp[10001][101];

int solve(int sum, int idx) {
    int &ret = dp[sum][idx];
    if(sum == k) return 1;
    if(sum > k) return 0;
    if(ret != 0) return ret;

    ret = 0;

    for(int i = idx; i < n; i++) {
        ret += solve(sum + vec[i], i);
    }
    return ret;
}

int main() {
    cin >> n >> k;

    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;

        vec.push_back(a);
    }

    cout << solve(0, 0);
}

 

이후 점화식으로 세워 통과한 코드

#include<bits/stdc++.h>

using namespace std;

int n, k;

vector<int> vec;
int dp[10001];

int solve() {
    dp[0] = 1;
    for(int i = 0; i < n; i++) {
        for(int j = vec[i]; j <= k; j++) {
            dp[j] += dp[j - vec[i]];
        }
    }

    return dp[k];
}

int main() {
    cin >> n >> k;

    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;

        vec.push_back(a);
    }

    cout << solve();
}

 

 

---

 

 

3. Feedback

- DP는 항상 재귀로 풀어야한다는 생각을 깨준 문제였다.

- 시간 복잡도만 생각하고 풀어왔지만 앞으로는 메모리도 확인해야겠다