Baekjoon 17626번 Four Squares

문제

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

걸린 시간

00 : 56 : 41 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int cache[50001]; // index : 값, value : 최소 개수의 제곱수

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cache[i] = i; // 1의 제곱으로만 구성된 개수
        for(int j = 1; j*j <= i; j++)
            cache[i] = min(cache[i], cache[i-j*j]+1);
    }
    cout << cache[n] << "\n";
    return 0;
}

반복적인 dp 를 사용한 풀이로, 1부터 찾으려는 수(n) 까지 최소 개수의 제곱수들을 캐쉬에 저장해 나간다.

1. cache[n]을 12 으로만 이루어진 최대 개수 n으로 초기화한다.
2. n보다 작거나 같은 거듭제곱의 수들을 12 부터 차례대로 n에서 줄여나가며 제일 작은 값을 선택한다.

n이 5일때를 예로 들면 다음과 같다.

// 1번
cache[5] = 5;
// 2번
cache[5] = min(cache[5], cache[5-1]+1) // 1의 제곱
cache[5] = min(cache[5], cache[5-4]+1) // 2의 제곱
// 정답 : 2

처음 문제를 풀이할 때 '최소' 개수의 제곱수들을 찾는 최적화 문제임에도 이를 무시하고 주먹구구식으로 코딩을 했다.

낮은 티어의 문제라고 해서 대충 생각했던 것 같다. 돌이켜보니 시도했었던 방법은 탐욕적 알고리즘이였지만 앞서 말했듯이 주먹구구식 접근이였기에 정당성 증명은 생각조차 하지 않았다...