#2294 동전 문제도 #2293 동전 문제와 비섯합니다. 단, 가치가 같은 동전이 주어질 수 있다는 것 뿐으로 크게 고려 대상은 아닙니다.
문제의 링크입니다.
https://www.acmicpc.net/problem/2294
2294번: 동전 2
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주
www.acmicpc.net
참고할 수 있는 이전 문제 링크입니다.
[C/C++] 백준 #2293 동전 1(동적 계획법)
동전들을 가지고 만들 수 있는 돈의 액수의 경우의 수는 동적 계획법을 이용하는 대표적 문제 중 하나입니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어
sdev.tistory.com
이번 문제는 경우의 수 문제가 아니고, 가장 적은 개수의 동전으로 만드는 것입니다.
\(v_{n, k}\)라는 배열을 정의했습니다. \(v_{n,k}\)는 n개의 주어진 동전을 가지고 k라는 값을 만들 수 있는 최소 동전의 개수입니다.
\[ v_{*, 0} = 0 \]
\[ v_{i, s} = min ( v_{n, s-c_i} + 1, v_{n-1, s} ) \]
형태로 설정을 했습니다.
이전의 \(v_{n, k}\)을 받아야 하지만, 저는 오름차순 형태로 처리를 함으로써, 해당 문제를 해결했습니다. 점근적 시간 복잡도는 \(O(NK)\) 입니다.
제가 작성한 소스입니다.
//--------------------------------------------
// baekjoon #2294
// - by Aubrey Choi
// - created at 2019-09-11
// - modified at 2021-07-16
//--------------------------------------------
#include <stdio.h>
int MIN(int a, int b) { return a<b?a:b; }
int main()
{
int n, k, s, v[10001];
scanf("%d%d",&n,&k);
for(int i=0;i<=k;i++) v[i]=100000;
v[0]=0;
while(n--)
{
scanf("%d",&s);
if(s>k) continue;
for(int i=s;i<=k;i++) v[i]=MIN(v[i-s]+1, v[i]);
}
printf("%d\n", v[k]==100000?-1:v[k]);
}
'Programming > BOJ' 카테고리의 다른 글
[C/C++] 백준 #2312 수 복원하기(수학) (0) | 2023.04.20 |
---|---|
[C/C++] 백준 #2302 극장 좌석(동적 계획법) (0) | 2023.04.20 |
[C/C++] 백준 #2293 동전 1(동적 계획법) (0) | 2023.04.20 |
[C/C++] 백준 #2290 LCD Test(구현) (0) | 2023.04.20 |
[C/C++] 백준 #2268 수들의 합 7(세그먼트 트리) (0) | 2023.04.19 |
댓글