백준(C언어)/23년 7월
[C] 백준 - 9084번: 동전
C0MPAS
2023. 7. 24. 14:42
7월 24일(월) - 다이나믹 프로그래밍 (9084번)
9084번: 동전
우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는
www.acmicpc.net
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
최초 생각 정리
- 다이나믹 프로그래밍 형식을 활용한 풀이를 예상
- dp[ i ] 를 구해야하는 경우, dp[ i ] = dp[ i ] + dp[ i - cost[ j ] ] 형태의 식을 얻어낼 수 있다
- 입력은 테스트케이스마다 N과 N가지의 동전 금액, 그리고 만들어야하는 금액인 M을 입력받는다
- 테스트케이스마다 배열 dp는 0으로 초기화해준 다음, 이중 for문을 돌리면서 모든 경우의 수를 카운팅한다
- 출력은 테스트케이스마다 방법의 수를 모두 구해서 dp[ M ]을 출력한다
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
문제점
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
풀이
#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <stdio.h>
int main(void)
{
int T;
scanf("%d", &T);
for (int i = 0; i < T; i++)
{
int N;
scanf("%d", &N);
int cost_of_N[21];
for (int j = 1; j <= N; j++)
{
scanf("%d", &cost_of_N[j]);
}
int M;
scanf("%d", &M);
int dp[10001] = { 0, };
dp[0] = 1;
for (int j = 1; j <= N; j++)
{
for (int k = cost_of_N[j]; k <= M; k++)
{
dp[k] = dp[k] + dp[k - cost_of_N[j]];
}
}
printf("%d\n", dp[M]);
}
return 0;
}ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ