개발 블로그

문제 링크 : www.acmicpc.net/problem/1699

문제

어떤 자연수 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

제곱수를 기준으로 생각했을 때, 항의 개수가 최소가 되려면 그 제곱수를 반드시 포함해야 한다고 생각했다.

예를 들어 18을 제곱수로 나타낸다고 하면, 

16<18<25 이기 때문에 18을 나타내려면 무조건 16이 들어가야한다고 생각했다.

그런데 예외로 18 = 9+9 로 16+1+1 보다 더 짧게 나타낼 수 있었다.

접근 방법 2 

18 을 자연수 2개의 합으로 나타낸다고 했을 때, 그 경우의 수를 모두 검사해서 최소가 될 때를 찾았다.

(1, 17)

(2, 16)

(3, 15)

(4, 14)

(5, 13)

(6, 12)

(7, 11)

(8, 10)

(9, 9) 

그러나 시간 초과가 떴다. 다시 생각해보니 이 중에 최소가 될 수 있는 후보는 제곱수가 포함된 경우였다.

그래서 1,4,9,16이 포함된 경우만 다시 검사해서 최소일 때를 찾아주었다.

즉,

dp[18-1] + dp[1]  => (16+1)+1

dp[18-4] + dp[4] =>  (9+4+1)+4

dp[18-9] + dp[9]  => 9 + 9

dp[18-16] + dp[16] => (1+1)+16

#include <iostream>
#include <algorithm>

using namespace std;

int dp[100489] = {0};

int main(){
     for(int i = 1; i<=100000; i++){
         dp[i] = 10000;
     }
    
    int N;
    cin >> N;

    dp[0] = 0; dp[2] = 2; dp[3] = 3;
    for(int i = 1; i*i<=100000; i++){
        dp[i*i] = 1;
    }
    
    for(int i = 1; i<=316; i++){
        for(int j = i*i+1; j<=(i+1)*(i+1)-1; j++){
            for(int k = 1; k<=i; k++){
                dp[j] = min(dp[j], dp[j-k*k] + dp[k*k]);
            }
        }
    }

        cout << dp[N];

    
    
    return 0;
}