[C#] 백준 9084번 동전

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

9084번: 동전

백준 문제 링크이며, 3067번 Coins와 같은 문제 입니다.

문제 난이도는 solved.ac에 골드 5 난이도로 되어 있습니다.

 

이 문제는 DP로 해결하는 문제이며,

DP 중 배낭 문제(냅색 문제)입니다.

---

문제를 간단히 설명하면,

동전들과 금액이 주어집니다.

동전들로 주어진 금액을 만들 수 있는 모든 경우의 수를 찾는 문제입니다.

 

편의를 위해 방법의 수는 2^31 - 1 보다 작고, 같은 동전이 여러 번 주어지는 경우는 없습니다.

 

입력

• 동전 3개(5, 7, 11)
• 금액 : 22

동전 5, 7, 11이 있고, 22원을 만들 수 있는 모든 경우의 수를 찾으면 됩니다.

 

[사진 1] 코드

T는 테스트 케이스 수,

N은 동전의 개수,

일차원 배열 coins는 동전,

M은 금액,

일차원 배열 dp의 각 인덱스 금액는 해당 인덱스를 만들수 있는 경우의 수를 저장합니다.

예를 들면, dp[100]은 동전들로 100을 만들수 있는 경우의 수 입니다.

 

coins의 크기는 N, dp의 크기는 10001로 초기화 해줍니다.

dp[M]이 이 문제의 정답이 될 것 입니다.

 

천천히 적으면서 문제를 풀어보겠습니다.

 

동전 하나씩 확인하면서 금액을 만들 수 있는지 확인합니다.

표로 보겠습니다.

 

[사진 2] 경우의 수(dp) 표

5 - 7 - 11 순으로 확인합니다.

 

10을 만드는 경우의 수는 5를 만드는 경우의 수에 5 동전을 넣어주면 됩니다.

 

17를 만드는 경우의 수는 12를 만드는 경우의 수에 5 동전을 넣어주거나,

10을 만드는 경우의 수에 7 동전을 넣어주면 됩니다.

 

5 동전부터 시작하겠습니다.

 

①

dp[5]는 5 동전 하나로 만들 수 있습니다. (dp[5] = 1)

 

②

dp[10] += dp[5] + 5 동전, 

5를 만들 수 있는 경우의 수를 10에 더해줍니다. (dp[10] = 1)

현재 dp[5]는 1이며, dp[10]은 0이기 때문에 dp[5] + dp[10] = 1 입니다.

 

dp[15] += dp[10] + 5 동전,

10을 만들 수 있는 경우의 수를 15에 더해줍니다. (dp[15] = 1)

현재 dp[10]는 1이며, dp[15]은 0이기 때문에 dp[10] + dp[15] = 1 입니다.

 

dp[20] += dp[15] + 5 동전,

15를 만들 수 있는 경우의 수를 20에 더해줍니다. (dp[20] = 1)

현재 dp[15]는 1이며, dp[20]은 0이기 때문에 dp[15] + dp[20] = 1 입니다.

 

즉, 5 동전으로 5, 10, 15, 20을 만들 수 있습니다.

 

위와 같은 방법으로 7 동전으로 7, 12, 14, 17, 19, 21, 22를 만들 수 있습니다.

 

①

dp[7]은 7 동전 하나로 만들 수 있습니다. (dp[7] = 1)

 

②

dp[22] += dp[15] + 7 동전,

15를 만들 수 있는 경우의 수를 22에 더해줍니다. (dp[22] = 1)

현재 dp[15]는 1이며, dp[22]는 0이기 때문에 dp[15] + dp[22] = 1 입니다.

 

11 동전으로 11, 22를 만들 수 있습니다.

 

①

dp[11]은 11 동전 하나로 만들 수 있습니다. (dp[11] = 1)

 

②

dp[22] += dp[11] + 11 동전,

11을 만들 수 있는 경우의 수를 22에 더해줍니다. (dp[22] = 2)

현재 dp[11]는 1이며, dp[22]는 1이기 때문에 dp[11] + dp[22] = 2 입니다.

 

출력 값인 dp[22]는 2 입니다.

 

③

②를 dp[22] += dp[22 - 11 동전]으로 바꿀 수 있습니다.

왜냐하면, 동전을 넣는다고 경우의 수가 따로 증가하는 것이 아닌,

(돈 - n 동전)의 경우의 수만큼만 증가하기 때문입니다.

 

이걸 이제 코드로 설명하겠습니다.

 

[사진 3] 중요 코드

dp[coins[i]]++; 부분은 ①을 실행한 것입니다.

이때 dp[coins[i]] = 1;이 아닌 이유는 만약 동전이 2와 4처럼 배수가 있을 경우 때문입니다.

2 동전에서 4가 만들어지는 경우의 수를 추가해놨는데, 4 동전에서 다시 1로 초기화 하면 안되기 때문에,

dp[coins[i]]++;으로 해줍니다.

 

이제 현재 동전으로 ③을 해줍니다.

현재 동전보다 작은 수는 만들 수 없기 때문에 j는 동전 숫자부터 시작해서 주어진 돈 M까지 반복합니다.

dp[j] += dp[j - coins[i]];로 j원을 i번째 동전으로 만들 수 있는 경우의 수를 계산해줍니다.

 

모든 동전을 dp[M]까지 계산해주고, dp[M]을 출력해주면 정답이 됩니다!!

---

제가 공부한 부분을 정리한 내용이기 때문에 틀린 부분 있을 수 있습니다!!

혹시 틀린 부분이 있으면 알려주세요!!