728x90
반응형
[ 다이나믹 프로그래밍 문제1 - 동전2 ] |
https://www.acmicpc.net/problem/2294
문제
n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.
사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
입력
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 ㅏㅈ연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.
출력
첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.
[ 풀이 ]
입력 데이터
3 8
1 4 6 이라고 하자
8원을 바꿔주는 데 필요한 동전 최소 개수는 2이다 (4원짜리 동전 2개이다)
1원 | 2원 | 3원 | 4원 | 5원 | 6원 | 7원 | 8원 | |
동전 1 | 1개 | 2개 | 3개 | 4개 | 5개 | 6개 | 7개 | 8개 |
동전 4 | 1개 | 2개 | 3개 | 4개 | 2개 | |||
동전 6 | 1개 | 2개 | 2개 |
※ 설명은 2차원 배열로 했지만 코딩할때는 1차원 배열로 하세요
[ 다이나믹 프로그래밍 문제2 - 동전1 ] |
https://www.acmicpc.net/problem/2293
<< 백준 2293 동전1 문제 소스보기 ↓ >>
더보기
#include <stdio.h>
int main()
{
int n, k;
int i, j;
int data[100], dy[10001] = {0,};
scanf("%d %d", &n, &k);
for(i=0;i<n;i++)
{
scanf("%d", &data[i]);
}
dy[0] = 1;
for(i=0;i<n;i++)
{
for(j=data[i];j<=k;j++)
{
dy[j] += dy[j-data[i]];
}
}
printf("%d\n", dy[k]);
return 0;
}
[ 풀이 ]
0원 | 1원 | 2원 | 3원 | 4원 | 5원 | 6원 | 7원 | 8원 | 9원 | 10원 | |
초기화 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1원 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
2원 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 5 | 6 |
5원 | 1 | 1 | 2 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 10 |
※ 1차원 배열로 코딩하세요
[ 다이나믹 프로그래밍 문제3 - 동전 ] |
<< 백준 9084 동전 문제 소스보기 ↓ >>
더보기
#include <stdio.h>
int main()
{
int t,coin[21], dy[10001];
int i, j, k, n, m;
scanf("%d", &t);
for(k=0;k<t;k++)
{
scanf("%d", &n);
for(i=1;i<=n;i++)
{
scanf("%d", &coin[i]);
}
scanf("%d", &m);
for(i=1;i<=m;i++)
{
dy[i] = 0;
}
dy[0]= 1;
for(i=1;i<=n;i++)
{
for(j=coin[i];j<=m;j++)
{
dy[j] += dy[j-coin[i]];
}
}
printf("%d\n", dy[m]);
}
}
[ 다이나믹 프로그래밍 문제4 - 동전0 ] |
https://www.acmicpc.net/problem/11047
반응형
'C언어 알고리즘' 카테고리의 다른 글
[동적계획법 6일차] 다이나믹 프로그래밍 - 기업투자 (0) | 2021.02.05 |
---|---|
[ 그리디(Greedy) 알고리즘 ] 그리디란? - 10문제 (0) | 2020.09.22 |
[동적계획법 문제풀이 1] - 문제 19 (0) | 2020.09.12 |
[동적계획법 3일차] 다이나믹 프로그래밍 ( 배낭문제 ) - 11문제 (0) | 2020.09.10 |
[동적계획법 1일차] 다이나믹프로그래밍 기초 - 7문제 (0) | 2020.09.10 |