반응형
https://www.acmicpc.net/problem/3067
3067번: Coins
우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해
www.acmicpc.net
[ 문제풀이 ]
이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.
https://rudalsd.tistory.com/20
[ 백준 ] 12865번 - 평범한 배낭 (C++)
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1
rudalsd.tistory.com
1. 점화식 dp[ i ][ j ] = dp[ i ][ j - coin[ i ] ] + dp[ i - 1 ][ j ] 을 통해 방법의 수를 구합니다.
2. dp[ N ][ M ] 을 출력합니다.
[ 소스코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | #include<iostream> using namespace std; int T; int coin[21]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> T; for (int t = 0; t < T; t++) { int N, M; cin >> N; int dp[21][10001] = { 0 }; for (int i = 1; i <= N; i++) { cin >> coin[i]; dp[i][0] = 1; } cin >> M; for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { if (j < coin[i]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = dp[i][j - coin[i]] + dp[i - 1][j]; } } cout << dp[N][M] << '\n'; } } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 2116번 - 주사위 쌓기 (C++) (0) | 2023.08.20 |
|---|---|
| [ 백준 ] 10216번 - Count Circle Groups (C++) (0) | 2023.08.19 |
| [ 백준 ] 16965번 - 구간과 쿼리 (C++) (0) | 2023.08.17 |
| [ 백준 ] 20007번 - 떡 돌리기 (C++) (0) | 2023.08.16 |
| [ 백준 ] 2224번 - 명제 증명 (C++) (0) | 2023.08.15 |