[2293] 동전 1 - C++

이번 문제는 잘못된 풀이 또한 함께 제시해 보려고 한다.

---

잘못된 아이디어

• 이차원 배열로 풀 수 있을 것 같다 DP [101][10'001]

이차원 배열은 불가능한 듯하다 

$$101 \times 10'001 \times 4 = 4'040'404byte = 4.040404mb$$

최대 4mb인데 4mb를 넘어가 버린다

점화식

$$dp [j][i] = dp [j][i-coin [j]]\; + \;dp [j][i]\; + \;\sum_{k = 1}^{j-1} dp [j-k][i-coin [j]]$$

 

답은 맞게 나온다 사실 맞는 지도 모른다..., 하지만 메모리 초과가 뜬다.... 그래도 열심히 풀었으니 코드는 올려본다

#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int n, k;
int coin[101];
int dp[101][10'001];

int main(){
  init();
  //입력
  cin >> n >> k;
  for(int i = 1; i <= n; ++i)
    cin >> coin[i];
  
  //연산
  for(int i = 1; i <= k; ++i){
    for(int j = 1; j <= n; ++j){
      if(i-coin[j] == 0)dp[j][i]=1;
      else if(i-coin[j] > 0){
        dp[j][i] = dp[j][i-coin[j]];
        for(int k = 1; k <= j-1; ++k)
          dp[j][i] += dp[j-k][i-coin[j]];
      }
    }
  }
  int cnt = 0;
  for(int i = 1; i <=n; ++i)
    cnt += dp[i][k];
  cout << cnt;

  return 0;
}

---

좋은 풀이

답을 보고 난 후의 풀이다.

 

coin = {1, 2, 5} 동전을 사용해 10원을 만들려 한다 동전의 순서는 신경 쓰지 않는다. (즉, 중복 불가능)

 

동전 coin [ i ]를 사용해 j의 가치를 만들 수 있는 경우의 수

• 1원을 사용해 1을 만들 수 있는 경우의 수 : 1개
• 1원을 사용해 2를 만들 수 있는 경우의 수 : 1개
• ...

0	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1

 

• 2원을 사용해 1을 만들 수 있는 경우의 수 : 0개
• 2원을 사용해 2를 만들 수 있는 경우의 수 : 1개
• 2원을 사용해 3을 만들 수 있는 경우의 수 : 2개
• ...

0	1	2	3	4	5	6	7	8	9	10
1	1	1 + dp[0]	1+dp[1]	1+dp[2]	1+dp[3]	1+dp[4]	1+dp[5]	1+dp[6]	1+dp[7]	1+dp[8]

• 5원을 사용해 1을 만들 수 있는 경우의 수 : 0개
• ....
• 5원을 사용해 5를 만들 수 있는 경우의 수 : 1개
• 5원을 사용해 6을 만들 수 있는 경우의 수 : 1개

0	1	2	3	4	5	6	7	8	9	10
1	1	2	2	3	3 + dp[0]	4+dp[1]	4+dp[2]	5+dp[3]	5+dp[4]	6+dp[5]

5를 사용하여 7을 만드는 경우의 수 => 7-5 = 2

= 2를 만드는 경우의 수 + 현재 dp [7]

결과

0	1	2	3	4	5	6	7	8	9	10
1	1	2	2	3	4	5	6	7	8	10

나의 생각으로는 애초에 처음부터 중복을 배재해 왔기 때문에 중복이 없는 것이라 생각한다.

 

점화식

$$dp [j] += dp [j-coin [i]]$$

---

CODE

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int n, k;
int coin[101];
int dp[10'001];

int main(){
  init();
  cin >> n >> k;
  for(int i = 1; i <= n; ++i)
    cin >> coin[i];
  dp[0] = 1;
  for(int i = 1; i <= n; ++i){
    for(int j = coin[i]; j <= k; ++j){
      dp[j] += dp[j-coin[i]];
    }
  }
  cout << dp[k];
  
  return 0;
}