문제 설명

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

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

입력

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

출력

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

문제 풀이

문제를 보자마자 아 1원짜리, 4원짜리, 9원짜리 등의 동전이 있는 동전 문제구나! 하는 것은 바로 알아차렸지만 괜히 그리디로 해결해보겠다고 시도하다 시간만 잡아먹었다. ‘동전 0’ 문제의 그리디 해결법은 각 동전이 다른 동전의 배수란 조건이 있었기에 가능했던 것을 몰랐었다.
아무튼 해결은 간단하다. ‘동전 1’ 문제와 같이 각 dp 배열에서 dp[i]와 dp[i-j]+1 중 작은 것을 배열에 넣어 최소값을 계속 갱신해주면 되는 문제이다. 자세한 코드는 다음과 같다.

코드

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n; cin >> n;
    double d=sqrt(n);
    int k=trunc(d);
    vector<int> dp(100006,100000);
    dp[0]=0;
    dp[1]=1; dp[2]=2; dp[3]=3;
    for(int i=1; i<=k; i++) {
        for(int j=i*i; j<=n; j++) {
            dp[j]=min(dp[j],dp[j-i*i]+1);
        }
    }//dp=현재 값과 dp[j-i]에서 동전을 더해준 값 중 작은것
    cout << dp[n];
}