BOJ 17626 : Four Squares

문제링크

풀이요약

DP

풀이상세

1. 1 부터 하나하나 씩 생각해보자.

   • 1 → 1개 ($1^2$)
   • 2 → 2개 ($1^2+1^2$)
   • 3 → 3개 ($1^2+1^2+1^2$)
   • 4 → 1개 ($2^2$)
   • 5 → 2개 ($2^2+1^2$)

2. 이를 달리 dp로 표현하는 경우 다음과 같다.

   • 1 → 1개 ($1^2$) ⇒ dp[1]=1
   • 2 → 2개 ($1^2+1^2$) ⇒ dp[2]=dp[1]+1
   • 3 → 3개 ($1^2+1^2+1^2$) dp[3]=dp[2]+1
   • 4 → 1개 ($2^2$) dp[4]=1
   • 5 → 2개 ($2^2+1^2$) ⇒ dp[5]=dp[4]+1

3. 단, 단순히 현재 수보다 작은 제곱 수+1 보다 그렇지 않은 경우가 더 갯수가 작은 경우도 있다. 12 의 경우 $3^2+1^2+1^2+1^2$ 보다 $2^2+2^2+2^2$ 가 갯수가 더 적다.

4. 따라서 현재 수보다 작은 모든 제곱의 수를 탐색하여, 제곱을 뺀 남은 수 중 가장 작은 값 + 1 하는 것으로 해당 dp[N] 의 값을 구할 수 있다.

#include <iostream>
using namespace std;
int N, dp[50004];

int main() {
    cin >> N;
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= N; i++) {
        int ret = 987654321;
        for (int j = 1; j * j <= i; j++) {
            ret = min(ret, dp[i - j * j]);
        }
        dp[i] = ret + 1;
    }
    cout << dp[N];
}