[C++] 백준 1699번:제곱수의 합(DP)

문제링크

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)

출력

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

 

풀이

DP를 이용하여 풀이한다.

모든 수는 1의 제곱수로 표현할 수 있기 때문에 미리 만들어둔 배열에 해당 index를 넣어주도록 한다.

이제 각 수를 만드는 제곱수의 합의 최소 개수를 아래와 같은 방법을 이용하여 갱신할 것이다.

index → 최소 개수

1 → 1

2 → 2

3 → 3

까지는 변함이 없다.

 

현재 4의 index에는 4가 들어가 있는 상태지만 사실 4는 2의 제곱이기 때문에 1개로 표현할 수 있다.

따라서 4 - 4를 나타낼 수 있는 수에 1을 더해주면 4를 표현할 수 있는 것이다.

다시 9를 예로 들어보겠다.

 

9는

1 : 3^2

2 : 2^2 + 2^2 + 1

3 : 1+1+1+1+1+1+1+1+1 세 가지의 방법이 있다.

 

현재 9의 index에는 세 번째의 경우 즉 9가 들어가 있는 상태이다.

 

두 번째 방법을 보면

9 - 4 = 5

5 - 4 = 1

5를 나타낼 수 있는 최소 경우의 수는 2이고 (1에 2^2를 더해주는 경우)

9를 나타낼 수 있는 최소 경우의 수는 3이 된다. (5에 2^2를 더해주는 경우)

 

세 번째 방법을 보면

9 - 9 = 0

0을 나타낼 수 있는 경우의 수는 0이며 여기에 3^3의 경우 +1을 해주어 1번만에 9를 만들어 낼 수 있다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 317^2 > 100000
int N;
int dp[100001];    // index를 만드는데 필요한 항의 최소 개수
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
     
    cin >> N;
 
    // A = 1 + 1 + ...
    for (int i = 1; i < 100001; i++) {
        dp[i] = i;
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j * j <= i; j++) {
            dp[i] = min(dp[i], dp[i - j * j] + 1);
        }
    }
 
    cout << dp[N];
 }

 

메모

DP가 코드는 단순하지만 거기까지 생각해내는 방법은 쉽지 않은 것 같다. 이번 주말에 다시 한 번 풀어보는 시간을 가져봐야겠다.

아래는 다른 DP문제입니다.

[C++] 백준 1463번:1로 만들기(DP)