[DP] 백준 #1699 / 제곱수의 합

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	7556	3115	2334	40.605%

문제

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

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

입력

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

출력

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

---

동전 알고리즘과 똑같은 메카니즘으로 풀어야한다.

[How To Solve?]

N을 기준으로, N보다 작은 모든 제곱수들을 N에서 뺀 값들을 살펴보아야 한다. 뭔소리냐고??

예를 들어, 12라는 숫자를 만들기 위한 최소한의 제곱수들의 갯수를 구하려면, 12보다 작은 제곱수들인 1, 4, 9를 12에서 뺀 값의 dp배열을 확인해봐야 한다.

왜냐고? dp[12]를 구하기 위해서 dp[12-1], dp[12-4], dp[12-9]의 대소비교를 통해, 가장 작은 값을 찾으면 해당 dp값에서 갯수를 하나 늘리면 최소로 필요로하는 제곱수의 갯수가 나오기 때문이다.

의문점 1) 왜 저렇게 하면 최소가 나오는가?

- DP문제들은 대부분 dp[n]을 구하기 위해서 dp[n-1]에서 +1이 정답인 경우가 많다.

- 같은 패턴이라고 생각했을 때, 여기서는 n-1이 아니라, 모든 제곱수가 후보가 될 수 있다.

- 그 이유는, 만약 위에서처럼 12를 구하기 위해서 11을 구성하는 최소의 제곱수에다가 1이라는 제곱수를 더하면 최소가 될 것이고

- 8을 구성하는 최소의 제곱수에 4라는 제곱수를 더해주면 최소가 될 것이고

- 3을 구성하는 최소의 제곱수에 9라는 제곱수를 더해주면 최소가 되기 때문이다.

- 위의 세 가지 경우 모두 마지막 경우에서 갯수가 하나 늘어나는 방식이기 때문에 후보군이 될 수 있는 것이다.

의문점 2) 그렇다면 초기 값은 어떻게 잡아야 하는가?

- 우선, N보다 작거나 같은 제곱수가 2개 이상일 때, 반복문으로 대소비교를 할 수 있다고 생각했다.

- 그 이유는 다음과 같다.

1 = 1

2 = 1+1

3 = 1+1+1

4 = 4

- 위에서 잘 보면, 3에서 4로 넘어가는 순간 가능한 제곱수는 1과 4로 총 두 개가 된다.(문제에서 N이 자연수라고 줬기 때문에 0은 제외한다)

- 즉, 1,2,3까지는 어떠한 변수도 적용되지 않고 항상 고정된 값으로 보아도 무방하다는 것이다.

[Code]

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class boj_1699 {
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine().trim());
        int dp[] = new int[N+1];
        
        for(int i=0;i<=N;i++)
            dp[i] = i;
        
        for(int i=4;i<=N;i++) 
            for(int j=2;Math.pow(j, 2)<=i;j++) 
                dp[i] = Math.min(dp[i], dp[(int) (i-Math.pow(j, 2))]+1);
        System.out.println(dp[N]);
    }
}