[BOJ 17626] Four Squares (C++)

Four Squares (Silver 4)

문제

전체 문제 보기

17626번: Four Squares

접근법

이 문제는 완전탐색 혹은 DP로 풀 수 있습니다. 여기서는 DP로 접근하여 풀었습니다. DP로 풀기 위해서 점화식은 다음과 같이 정리할 수 있습니다.
\[f(n) = \mbox{min}(f(1 * 1) + 1 , f(2 * 2) + 1, ... ,f(\sqrt{n} * \sqrt{n} + 1)\]

 

전체 구현

아래와 같이 구현하여 문제를 해결할 수 있습니다.

#include <iostream>
#include <array>
#include <algorithm>
#define endl '\n'
using namespace std;
const int MAX = 50'001;
const int INF = 99'999;

int main() {
    // 입출력 성능 향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int n; // 1 ≤ n ≤ 50,000
    cin >> n;  
    array<int, MAX> cache{};
    cache.fill(INF);
    cache[0] = 0;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j * j <= i; j++)
        {
            cache[i] = min(cache[i], cache[i - j * j] + 1);
        }
    }
    
    cout << cache[n];
    return 0;
}