BOJ 백준온라인져지 1699 제곱수의 합 풀이

문제 설명 

1. 어떤 수 N 이 있을 때, 그 N 을 만들 수 있는 제곱수들의 합의 최소 개수를 구하면 되는 문제다.

풀이

1. dp 로 풀었다. dp 완전탐색

dp[i] = 답

답 = 1 or dp[i - j * j] + dp[j * j] (1 <= j * j <= i)

증명

1. dp[2] = dp[1] + dp[1] 이다.

2. dp[3] = dp [1] + dp[2] 이다.

결론적으로는 각 단계에서 구해놨던 최적해를 이용해서 우리가 구하고자 하는 최적해를 구할 수 있다는 것이다.

만약 N 이 10이라고 가정하면 답은 2 일 것이다.

그런데 구하는 과정이 어떻게되냐?

dp[i - j * j] + dp[j * j] (1 <= j * j <= i) j 를 증가시키면서 값을 업데이트 해주는데 저 조건에 해당하는 값은 제일 높은 값은 j = 3 일 때 이다.

j = 3 일 때 dp[9] + dp[1] 이 되므로 i 가 N 까지 도달하면서 이미 구해놨던 답을 기반으로 구할 수 있다. dp[9] 는 3 * 3 이므로 1 로 변경한다.

코드

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

예제 입력 1 

7

예제 출력 1 

4

출처

ACM-ICPC > Regionals > Asia > Korea > Nationwide Internet Competition > Asia Regional - Daejeon Nationalwide Internet Competition 2007 E번