백준 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일 고민할줄이야.. ㅠㅠ
아직 배울게 많다고 느껴진다.