코드 복사/붙여넣기 하는 당신이 아름답습니다.

13910 : 개업

풀이

웍을 최대 2개까지 사용할 수 있으므로 가능한 조합을 모두 구해둔다

그리고 점화식 세워서 풀면 된다.

dp[n] = min(dp[n-i]+1,dp[n])

코드

#include <stdio.h>
int main() {
	int n, m, i, j, a[101], dp[10001];
	bool chk[22222] = { 0 };
	scanf("%d %d", &n, &m);
	for (i = 0; i <= n; i++) dp[i] = 1e9; chk[0] = 1; dp[0] = 0;
	for (i = 0; i < m; i++) scanf("%d", &a[i]);
	for (i = 0; i < m; i++) {
		chk[a[i]] = 1;
		for (j = i + 1; j < m; j++) chk[a[i] + a[j]] = 1;
	}
	for (i = 1; i <= n; i++) {
		if (!chk[i]) continue;
		for (j = i; j <= n; j++) dp[j] = dp[j] < dp[j - i] + 1 ? dp[j] : dp[j - i] + 1;
	}
	printf("%d", dp[n] != 1e9 ? dp[n] : -1);
	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge

wookje.kwon's profile image

wookje.kwon

2017-05-31 11:56

Read more posts by this author