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

1699 : 제곱수의 합

풀이

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

wookje.kwon's profile image

wookje.kwon

2017-08-06 20:06

Read more posts by this author