[BOJ] 1699번 : 제곱수의 합 (C++)

https://www.acmicpc.net/problem/1699

1699번: 제곱수의 합

1 = 1*1

2 = 1*1 + 1*1

3 = 1*1 + 1*1 + 1*1

4 = 2*2

5 = 2*2 + 1*1

6 = 2*2 + 1*1 + 1*1

7 = 2*2 + 1*1 + 1*1 + 1*1

8 = 2*2 + 2*2

9 = 3*3

 

이렇게 나타낼 수 있다. 

그래서 

d[1] = 1

d[2] = d[2-1]+1 = 2

d[3] = d[3-1]+1 = 3

d[4] = d[4-4]+1 = 1

d[5] = d[5-4]+1 = 2

d[6] = d[6-4]+1 = 3

d[7] = d[7-4]+1 = 4

d[8] = d[8-4]+1 = 2

d[9] = d[9-9]+1 = 1

 

일반화해보자면, 현재 구하고자 하는 수가 i이고 i보다 작거나 같은 제곱수가 j라고 할 때

d[i] = d[i - j*j] + 1 이 된다.

+1이 되는 이유는 이미 j*j라는 수를 한 번 이용했기 때문이다.

i에서 j*j만큼 사용했기 때문에 i-j*j 라는 수를 제곱수들의 합으로 표현할 때 최소개수를 구해주면 된다. 

 

그래서 우리는 i보다 작은 제곱수를 찾아야한다. 

소수구하기 문제를 풀어봤다면 알겠지만 제곱수를 찾는 방법은 이중포문을 돌려야 하는데, 시간복잡도를 루트를 씌운 효과를 내게 할 수 있는 방법이 있다. 

이중포문에서  outer포문이 i, inner포문이 j 라고 할 때, j*j<=i 라고 조건을 주는 방법이다.

이렇게 i보다 작거나 같은 제곱수가 될 수 있는 모든 j를 찾아야 한다.

왜냐하면, i보다 작거나 같은 제곱수 중에서 가장 큰 j가 정답이 아닐 때가 있기 때문이다.

예를 들어, i=52라고 해보자.

52보다 작거나 같은 제곱수 중에서 가장 큰 수는 49이다.

d[52] = d[52-49]+1 = d[3]+1 = 4 가 된다.

그러나 d[52] = d[52-36]+1 = d[16]+1 = 2 가 최소개수가 된다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int d[100005];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;

    for(int i=1; i<=n; i++){
        d[i]=0x7fffffff; //아주 큰수로 초기화
        for(int j=1; j*j<=i; j++){
            d[i] = min(d[i], d[i-j*j]+1);
        }
    }

    cout<<d[n];
}

 

d[i]에는 지금 구하고자 하는 j보다 작은 j들을 검사하여 그 중 가장 작은 값을 넣어놓게 된다. 

그래서 현재까지 가장 최소개수가 들어있는 d[i]와 d[i-j*j]+1 중에서 가장 작은 값을 검사하게 된다.

 

 

회고)

처음에 무조건 i보다 작거나 같은 제곱수 중에서 가장 큰 j를 찾고 그게 정답인 줄 알았다. 

그래서 모든 j가 아닌 딱 하나의 j를 가지고 d[i-j*j]+1를 해주게 되어 틀렸다. 

그래도 일반화한 식이랑 j*j<=i를 이용하여 제곱수 구하기는 잘 구현했었다.

52와 같은 예시를 생각해냈으면, i보다 작거나 같은 모든 제곱수에 대해 검사를 하였을텐데 

문제에 나와있는 예제들로는 그렇게 생각할 수 없어서 거의 다 생각해냈지만 결국 풀지 못한 게 아쉽다.