백준 1699번 제곱수의 합 (C++)

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

1699번: 제곱수의 합

문제 해석은 다음과 같다. 

1. 11을 제곱수로 나타내는 방법은 여러가지가 있는데, 대표 예시로 아래 두개를 봐보자.

11 = 3^2 + 1^2 + 1^2 (3개 항)

11 = 2^2 + 2^2 + 1^2 + 1^2 + 1^2 (5개 항)

2. 숫자 n이 주어졌을 때, n을 제곱수로 나타낼 수 있는 항의 최소 개수를 구하라.

 

문제 풀이는 다음과 같다. 

    for(int i=1; i<=n; i++){
        arr[i] = i;
        for(int j=1; j*j<=i; j++){
            if(arr[i]>arr[i-j*j]+1) arr[i] = arr[i-j*j]+1;
        }
    }

1. 이중 for문을 구현한다. 이때 첫 번째 for문의 최대 범위는 n까지이다.

2. 모든 숫자는 1의 제곱수 * 해당 숫자만큼의 갯수로 구현할 수 있이므로, arr[i] = i로 선정된다.

3. 두 번째 for문의 조건을 보자. j=1, j*j<=i인데, 어떤 숫자 i의 루트를 구한 값으로 제곱수를 구현할 수 있으므로 j*j<=i가 나오게 된다.

4. 우리의 목적은 제곱수의 최소 항을 구하는 것이다. 예를들어 n=4를 가정해보자.

 if(arr[i]>arr[i-j*j]+1) arr[i] = arr[i-j*j]+1;

arr[2] = 2이고, arr[4-2*2] = arr[0] = 0이다. arr[0]+1은 1인데, 여기서 +1이 붙은 이유는 4, 즉, 2의 제곱수인 4가 1개로 들어가기 때문이다. arr[4] = 4 보다 arr[4-2*2]+1 = 1이 더 작으므로, arr[4] = 1이 들어가게 된다.

 

#include <iostream>
#define MAX 100001
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n = 0, arr[MAX];
    cin >> n;
    for(int i=1; i<=n; i++){
        arr[i] = i;
        for(int j=1; j*j<=i; j++){
            if(arr[i]>arr[i-j*j]+1) arr[i] = arr[i-j*j]+1;
        }
    }
    cout << arr[n] << "\n";
    return 0;
}