백준 2293
https://www.acmicpc.net/problem/2293
처음 풀어보는 골드문제다!
고민하고 머리싸매도 안풀리길래 그냥 구글링했다.
다른 분께서 쓰신 글을 토대로 알고리즘을 작성했다.
https://bitwise.tistory.com/504
dp 를 동전 수만큼 업데이트 하면서 풀면 된다.
여기서 dp[1] 는 1원을 만들 수 있는 경우의 수,
dp[2] 는 2원을 만들 수 있는 경우의 수를 의미한다.
예를 들어 입력된 값이
3 10
2
3
5
라고 했을때 dp는 아래 gif처럼 n번 업데이트된다.
최종적으로 dp[10] 을 구하면 문제가 풀린다.
입력된 k만큼 dp의 초기값을 0으로 설정한다.
이때 dp[0] 은 0원을 만들 수 있는 경우의 수가 되는데, 1으로 초기화 해야 한다.
이제 하나하나 살펴보자.
2원 하나로 만들 수 있는 k의 값을 구하는 경우의 수이다.
dp[coin[0]] 에서 시작해 값을 업데이트하는 것을 볼 수 있다.
이제 2,3원으로 k의 값을 구하는 경우의 수이다.
3원의 경우도 이와 비슷하게 coin[1] 에서 시작해 이미 입력되어 있는 dp를 기반으로 업데이트된다.
이제 코드를 짜면 다음과 같다.
성공한 코드 :
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main() {
int n, k;
int coin[100], dp[10000];
scanf("%d %d",&n,&k);
for (int i = 0; i < n; i++) {
scanf("%d", &coin[i]);
}
// 초기 경우의 수 설정
for (int i = 1; i <= k; i++) {
dp[i] = 0;
}
dp[0] = 1;
// 점화식
for (int i = 0; i < n; i++) {
for (int j = coin[i]; j <= k; j++) {
dp[j] = dp[j] + dp[j - coin[i]];
}
}
// 결과출력
printf("%d", dp[k]);
}
후기 :
생각보다 간단하고 짧은 알고리즘이었다니..
이렇게 쉬운걸 2~3일 고민할줄이야.. ㅠㅠ
아직 배울게 많다고 느껴진다.
Author And Source
이 문제에 관하여(백준 2293), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hw020123/백준-2293저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)