풀이
웍을 최대 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