풀이
knapsack 풀듯이 똑같이 풀면 된다!
배낭에 무게가 i*i이고 가치가 1인 돌덩이들을 넣는다고 생각하자!
dp[j] = min(dp[j-i*i] + 1, dp[j])
코드
#include <stdio.h>
int n, d[100001];
int min(int a, int b) { return a < b ? a : b; }
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) d[i] = 1e9;
for (int i = 1; i*i <= n; i++) for (int j = i*i; j <= n; j++)
d[j] = min(d[j - i*i] + 1, d[j]);
printf("%d", d[n]);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge