[백준] 2293번 동전 1

문제

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

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.

 

 

이 문제... 힘들었다.

이해하는 시간이 더 오래 걸렸던것 같다.

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

뭔가 이상하다. 

현재 이 표는 세부적인 것을 고려하지 않았다. 예를들어 3원 같은경우를 보면

1 + 2 , 1원들  이렇게 2가지가 존재하는데 0이라니 어디서 부터 잘못된걸까?

 

최초로 2원을 사용하는 곳이 어디일까? 바로 2원을 만들때다. 어차피 3원을 만들때

1 원 이랑 2원이 필요하기 때문에 2원 것을 빌리자ㅎㅎ

그럼 총 경우의 수가 3개가 된다. 

 

5원 무시중

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

 

뭐 이런식으로 나온다.

 

이제 5원을 채워보자.

 

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

 

 

아 힘들다. 여기서 우리가 알 수 있는건

전체 값에서 동전의 번호?를 빼주면 된다는 사실이다.

이게 왜 이렇게 되냐면

2원으로 3원을 만든다고 할때

1x3 , 1x1 + 2x1   이렇게 총 2가지가 나온다.

그런데... 이거 어디서 봤을까?

바로 2원을 구할때랑 갯수가 똑같다. 다시 말하면 1원의 값과 2원의 값을 더한 형태라고 생각할 수 있다.

 

그럼 그들을 활용하면 어떨까?

어차피 갯수도 같은데 그냥 쓰면 되지 않을까?

 

4원 같은 경우는 그냥 2x2가 추가된것일 뿐이다. 

 

그러면 우리는

2원일때는 항상 2를 빼주면 되지 않을까? 아.... 이게 또 무슨 소리냐면

어차피 2의 배수가 아니면 2가 영향을 줄 수 있는 방법은 zero다 그렇기 때문에

계산한 값에서 2를 계속해서 빼주면 된다.

물론 5도 마찬가지다.

 

 

그러니까 검색해서 찾아준다고 생각하면 편할 듯 싶다.

 

그러면 2원은

i - 2;가 되고

 

10 = 8

9 = 7

8 = 6

....

 

5원은

i - 5;가 된다. 참고로 i는 미지수다.

 

 근데 이렇게만 하면 전체를 구할 수 없다. 그렇기 위해서는

 

dp를 이용해서 풀어야 한다. 어차피 이 안에 다있을테니...

 

저 2개의 식은 2와5에 사용될 동전의 갯수에 불과하다.

 

이제 이렇게 구한것으로 합을 구하면?

 

dp[j] += dp[j-2];

dp[j] += dp[j-5];

가 된다.  i라 생각했는데 쩝 틀렸군... ㅜㅜ

 

 

그럼 점화식은 dp[n] += dp[n-k]가 된다.

아니 시그마 n-k 가 된다.

이걸 dp로 수정한게 첫번째..

 

자 이제 코드를 보자.

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

int dp[10001];
int main(void) {
  int n,k;
  cin >> n >> k;

  int coins[n];

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

  cout << dp[k] << "\n";
} 
 

 

시그마 n-k

 

dp[0]인 이유는 같으면  ????

 

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

int a[105];
int n,k;
vector<int> d1;
vector<int> d2; // 배열보다 vector가 값의 복사가 편함

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  d1.resize(k+1);
  d2.resize(k+1);
  for(int i = 0; i < n; i++) cin >> a[i];
  for(int t = 0; t <= k; t += a[0]) d1[t] = 1; // k 이하의 a[0]의 배수들에 대해 모두 경우의 수가 1가지 있음을 명시
  for(int i = 1; i < n; i++){
    fill(d2.begin(),d2.end(),0); // d2를 0으로 초기화
    for(int j = 0; j <= k; j++){            
      d2[j] = d1[j];
      if(j >= a[i]) d2[j] += d2[j-a[i]];
    }
    d1 = d2; // d1으로 d[i][..]을 옮김. 만약 배열로 하고 싶으면 그냥 for문 한번 돌면서 값을 옮기면 됨
  }
  cout << d1[k];
}

거참... 어렵군...

 

시그마 n-k