백준 2294

https://www.acmicpc.net/problem/2294

3시간동안 삽질했다.. 그래도 해결 안되고 모르겠어서 구글링해보니까 아래처럼 짜면 된다고 한다.
동적 프로그래밍(dynamic programming) 으로 풀면 되는 문제라고 한다.
동적 프로그래밍에 대해서는 이분이 작성한 글을 읽어보자. https://hongjw1938.tistory.com/47

다른 분께서 작성하신 알고리즘 설계 방법이다. 이것도 읽어보면 좋을듯
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=occidere&logNo=220794872664

코드를 따라가 보면서 이해하자.

성공한 코드 :

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int min(int a, int b) { return (a > b) ? b : a; }

int main() {
	int N, K;
	int dp[10001];
	int coin[101];
	
	dp[0] = 0;
	for (int i = 1; i < 10001; i++) {
		dp[i] = 100001;
	}

	scanf("%d %d", &N, &K);
	for (int i = 0; i < N; i++) {
		scanf("%d", &coin[i]);
		for (int j = coin[i]; j <= K; j++) {
			dp[j] = min(dp[j], dp[j - coin[i]] + 1);
		}
	}

	if (dp[K] == 100001) printf("-1");
	else printf("%d", dp[K]);

	return 0;
}

느낀점 : 점화식을 찾는게 중요한 것 같다.