[BOJ] 백준 17626번 Four Squares 풀이

| |
백준 온라인 저지 백준 17626번 - Four Squares C++ 풀이


문제

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 5^2과 1^2의 합이다; 또한 4^2 + 3^2 + 1^2으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 125^2 + 6^2 + 1^2 + 1^2라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 105^2 + 15^2 + 8^2 + 5^2.

자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.


입력

입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 50,000이다.


출력

출력은 표준출력을 사용한다. 합이 n과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.


풀이

가장 첫번째로 해야하는 접근은 완전 탐색이다. 수가 주어지면 1부터 n을 넘지 않는 모든 제곱수를 골라보며 브루트포싱한다. 그러면 같은 수에 대하여 중복 계산이 어마어마하게 나온다는 것을 깨닫는다. 여기서 메모이제이션을 이용해 다이나믹 프로그래밍으로 접근할 것을 떠올린다. 그리고 추가적으로 문제에서 아래와 같은 사실을 알려준다.

“모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명되었다.”

따라서 재귀의 깊이가 4를 넘어가면 그 이후 경우의 수는 고려할 필요가 없다.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <cmath>
using namespace std;

int cache[50001];

int solve(int n, int cnt){
    if(n==0) return 0;
    if(cnt==4) return 1e9; // 반드시 답이 아님

    int& ret=cache[n]; // 메모이제이션
    if(ret!=0) return ret;

    ret=1e9;
    for(int i=1;i<=(int)sqrt(n);i++) // 브루트포스
        ret=min(ret,solve(n-i*i,cnt+1)+1);

    return ret;
}

int main(){
    int n; cin>>n;
    cout<<solve(n,0);
    return 0;
}
0%