This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<iostream> | |
| using namespace std; | |
| int dp[10001]; | |
| struct coin { | |
| int value; | |
| int count; | |
| }; | |
| int main() { | |
| int sum; | |
| int n; | |
| cin >> sum >> n; | |
| coin c[101]; | |
| dp[0] = 1; | |
| for (int i = 0; i < n; i++) { | |
| cin >> c[i].value >> c[i].count; | |
| } | |
| for (int i = 0; i < n; i++) { | |
| for (int j = sum; j >= 1; j--) { | |
| for (int k = 1; k <= c[i].count; k++) { | |
| if(j - c[i].value * k >= 0) | |
| dp[j] += dp[j - c[i].value * k]; | |
| } | |
| } | |
| } | |
| // 코인 종류 마다 반복문을 돌림 | |
| // 5 3 | |
| // 10 2 | |
| // 1 5 | |
| // | |
| // 1, 5, 10 에 대해 각각 한번씩 | |
| // 5의 반복문이 끝나면 dp[15] dp[10] dp[5]의 값이 1 | |
| // 만약 두 번째 for문이 오름차순으로 진행되었다면 dp[5]의 값 1, dp[10]의 값 2 dp[15]의 값이 3으로 되었을 거임 | |
| // 10의 반복문이 끝나면 dp[20] = 2 dp[15] = 2 | |
| // dp[20] += dp[20 - 10 * 1] | |
| // dp[20] += dp[20 - 10 * 2] | |
| // dp[15] += dp[15 - 10 * 1] | |
| // dp[10] += dp[10 - 10 * 1] | |
| // 1의 반복문이 끝나면 dp[20] = 4 | |
| // dp[20] += dp[20 - 1 * 5] | |
| // dp[15] += dp[15 - 1 * 5] | |
| // dp[15] += dp[10 - 1 * 5] | |
| cout << dp[sum]; | |
| } |
같은 종류의 코인으로 이미 계산된 dp 테이블 값을 중복으로 계산하는 것을 주의하자
