[백준 2293번] 동전 1 (java)

2293번: 동전 1

 

합이 k원이 되면서, 순서만 다르고 조합이 같은 경우는 하나의 경우로 여긴다. 

우선 각각의 동전의 가치를 coin 배열을 생성하여 차례대로 넣어주었다.

 

int[] coin = new int[n];

coin[0] = 1

coin[1] = 2

coin[2] = 5

 

이 문제를 다이나믹 프로그래밍으로 풀기 위해 점화식을 세웠다.

 

처음에는 합이 k원이 되는 조합을 dp[k]라고 할 때,

dp[k] = dp[k-coin[0]] + dp[k-coin[1]] + dp[k-coin[2]] + ... + dp[k-coin[n-1]] 

이런식으로 점화식을 세웠는데, 순서만 다르고 조합이 같은 경우가 다른 경우로 여겨진다는 문제점이 있었다.

 

예를 들어, dp[1] = 1, dp[2] = 2 이다. 1원이 되기 위해서는 1원 한개만 필요하고, 2원이 되기 위해서는 (1,1), (2) 이렇게 두 가지가 있기 때문이다.

그런데 dp[3] = dp[3-coin[0]] + dp[3-coin[1]] = dp[2] + dp[1] = 2 + 1 = 3이 되는데,

이 3에는 (1,1,1), (1,2), (2,1)가 포함된 것이다. 하지만 (1,2)와 (2,1)는 순서만 다르고 같은 경우이므로 중복해서 카운트되면 안된다.

 

---

 

만약 순서만 다르고 조합이 같은 경우를 중복시키지 않으려면 어떻게 해야할까?

 

동전을 한가지만 사용할 때의 경우의 수, 동전을 두가지 사용할 때의 경우의 수, 동전을 세가지 사용할 때의 경우의 수..동전을 n가지 사용할 때의 경우의 수

이런식으로 사용하는 동전의 가지 수를 늘려가면서 메모이제이션을 하면 된다.

 

먼저 1원짜리 동전만 이용하여 1원부터 k원까지 나타내는 경우의 수는 다음과 같다.

k원일 때 1원짜리 동전을 k개만큼 사용하는 1가지 경우의 수밖에 없다.

그 다음, 1원짜리 동전과 2원짜리 동전을 조합하여 나타낼 수 있는 경우의 수는 다음과 같다.

 

k = 1인 경우, 2원짜리 동전보다 작은 금액이므로 2원짜리 동전으로는 나타낼 수 없다. 

즉, k>=coin[i]일 때만 dp[k]의 값이 달라지게 된다.

 

k = 3일 때는 어떻게 될까?

기존에 1원짜리 동전만으로 나타냈을 때의 경우의 수는 1이었다. dp[3] = 1

3원을 만들기 위해 2원짜리 동전을 사용하는 경우는 k = 1일 때(dp[1])의 경우의 수와 같다.

k = 1일 때(dp[1])의 경우에서 2원짜리 동전만 추가하면 되기 때문이다.

 

따라서

dp[3](1원,2원짜리 동전으로 표현한 경우의 수) = dp[3](기존의 1원짜리 동전만으로 표현한 경우의 수) + dp[1] 이다.

이를 점화식으로 표현하면, k>=coin[i] 일 때 dp[k] = dp[k] + dp[k-coin[i]]로 표현할 수 있다.

 

1원짜리 동전, 2원짜리 동전, 5원짜리 동전을 모두 사용하여 k원 나타내는 경우의 수는 아래와 같다.

역시 마찬가지로 k가 5이상일 때, 5원짜리 동전을 사용할 수 있으므로 아래 표의 빨간색 부분의 경우의 수가 갱신된다.

 

 

전체 코드 :