[백준/C++] 17626번: Four Squares

문제

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

---

문제 요약

자연수 n이 주어졌을 때, n을 제곱수 합으로 나타낼 수 있는 최소 개수를 출력한다.

---

코드

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n;

// dp[i]: i를 제곱수 합으로 나타낼 수 있는 최소 개수
int dp[50050];

// n을 제곱수 합으로 나타낼 수 있는 최소 개수를 반환하는 함수
int dfs(int n) {
    // 0을 제곱수 합으로 나타낼 수 있는 최소 개수 = 0 
    if (n == 0) {
        return 0;
    }

    // 이미 dp[i]를 구했었다면, 바로 반환
    if (dp[n] != -1) return dp[n];


    // 아니라면, 완전 탐색(백트래킹)
    int min_cnt = 5;
    for (int i = 1; i * i <= n; i++) {
        min_cnt = min(min_cnt, 1 + dfs(n - i * i));
    }

    return dp[n] = min_cnt;

}

int main() {
    cin >> n;

    // dp 테이블 초기화
    memset(dp, -1, sizeof(dp));

    cout << dfs(n);

    return 0;
}

---

코드 설명

Top Down Dynamic Programming으로 문제를 해결한다.

 

n을 인자로 받고, n을 제곱수의 합으로 나타낼 수 있는 최소 개수를 반환하는 함수 dfs를 정의한다.

 

n보다 작은 제곱수 i * i를 모두 구하고, n을 (i * i) + (n - i * i)로 나눈다.

 

n을 제곱수의 합으로 나타낼 수 있는 최소 개수

= (i * i) + (n - i * i)을 제곱수의 합으로 나타낼 수 있는 최소 개수

 

이므로, 1 + dfs(n - i * i)를 구한다.

 

i를 제곱수 합으로 나타낼 수 있는 최소 개수를 저장하는 dp[i]를 생성하고, -1로 초기화한다.

(-1은 아직 값을 구하지 않았다는 의미이다.)

 

이미 답을 구했던 경우는 dp 테이블을 참조하여 중복 재귀를 방지한다.