[백준(BOJ)] Four Squares(17626번)_C++

문제푸는데 생각보다 애를 많이 먹었다.

처음에는 dp로 쉽게 풀 수 있을 줄 알았는데

n = 12일 때 arr[12] = arr[4] + arr[8] 이어야하는데 이것을 선택하도록 하는 방법을 생각해내질 못했다.

 

그래서 곰곰히 생각해보니 답이 1인 녀석들은 무조건 정해져있음을 알았다.

i = 1 ~ 50000^(1/2) 의 수들의 제곱일 때 arr[i] = 1이다.

 

그러면 답이 2인 녀석들도 정해져 있다.

arr[i + i] = 2이다.

 

그럼 답이 3인 녀석들도 정해져 있지 않은가?

답이 1인 녀석들이 i, 2인 녀석들이 j라고 하면 arr[i + j] = 3이다.

(당연히 답이 2와 3 모두 될 수 있는 놈들도 있으므로 작은 것을 선택하면 된다.)

 

그럼 나머지 녀석들은 답이 4다.

 

 

---

정답 코드

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int n, answer[50001];
vector<int> v1, v2;
//v1 : v1's element i is answer[i] = 1
//v2 : v2's element i is answer[i] = 2

int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    //input
    cin >> n;

    //init
    for (int i = 0; i <= 50000; i++)
        answer[i] = 4;

    //answer[i] = 1
    for (int i = 1; i <= sqrt(50000); i++){
        answer[i * i] = 1;
        v1.push_back(i * i);
    }

    //answer[i] = 2
    for (int i = 0; i < v1.size(); i++){
        for (int j = i; j < v1.size(); j++){
            if (v1[i] + v1[j] <= 50000){
                answer[v1[i] + v1[j]] = min(answer[v1[i] + v1[j]], 2);
                v2.push_back(v1[i] + v1[j]);
            }
        }
    }
    
    //answer[i] = 3
    for (int i = 0; i < v1.size(); i++)
        for (int j = 0; j < v2.size(); j++)
            if (v1[i] + v2[j] <= 50000)
                answer[v1[i] + v2[j]] = min(answer[v1[i] + v2[j]], 3);

    //output
    cout << answer[n];
}