(백준 2294번 동전2 C++) 라이님 블로그 대회 알고리즘 따라잡기 5) DP(Dynamic Programming) 동적계획법 6

내가 풀었다고 보기도 머쓱한 문제ㅎㅎ

 

이 문제의 풀이는 라이님 블로그를 무조건적으로 참고해야 한다!!!

 

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220777103650&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

동적 계획법(Dynamic Programming) (수정: 2019-02-07)

 

백준 2294번

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

2294번: 동전 2

 

그래도 풀이를 안 보고 혼자 풀려고 노력했다. 혼자 아예 안 보고 푸는데 3일 걸림..히히

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 101, MAX_M = 10001, IMPOSSIBLE = 100000000;
int N, K, DP[MAX_N][MAX_M], value[MAX_N]; 

int f(int n, int k) {
	if (DP[n][k] != -1) return DP[n][k];
	int result = f(n - 1, k);
	if(k >= value[n]) result = min(result, f(n, k - value[n]) + 1);
	DP[n][k] = result;
	return result;
}
int main() {
	scanf("%d %d", &N, &K);
	for (int i = 1; i < N+1; i++) scanf("%d", &value[i]); value[0] = 0;
	for (int i = 1; i < N+1; i++) {
		for (int j = 1; j < K+1; j++) {
			DP[i][j] = -1;
		}
	}
	for (int j = 0; j < K + 1; j++) DP[0][j] = IMPOSSIBLE;
	for (int i = 0; i < N + 1; i++) DP[i][0] = 0;

	int ans = f(N, K);
	if (ans != IMPOSSIBLE) printf("%d", ans);
	else printf("-1");
}

 

아 맞다..

라이님처럼 초기화하면 훨씬 빠르게,,, base case를 만들 수 있다..^^