BOJ - Four Squares(17626)

실버5 : 동적 계획법 문제이다.

생각

생각 보다 힘들게 푼 문제이다. n이 50000이고, 시간 제한이 0.5초이기 때문에 완전탐색으로 풀면 힘들 것이라 생각했다. 그래서 동적 계획법 방법으로 풀이를 채택했다.

이 문제는 동전 문제와 비슷하게 생각해야 한다. 결국 몇개의 제곱수가 최소로 필요하냐는 문제인데, 사실 1로 모든 수를 만들 수 있기 때문에 더해지는 숫자의 개수가 늘어남에 따라 최소 개수로 업데이트를 해주는 것이 맞다.

정의

dp[i] = i을 만드는데 있어 필요한 최소 숫자의 갯수

정의는 1차원 다이나믹이지만, 계속 업데이트를 해주어야 한다. 업데이트를 하게 되면 최종적으로 4번하면 i을 만드는데 있어 필요한 최소 제곱수의 갯수 로 정리될 수 있다. (문제에 이미 증명되었다고 한다)

점화식

dp[i] = min(dp[i], dp[j*j]+dp[i-j*j])

잘 생각해보자. n이라는 숫자를 만들기 위해 필요한 개수는 dp[n-i*i]로 부터 올 수 밖에 없다. 제곱수를 더하여 해당 수가 만들어지기 때문이다.

n = n-1*1 + 1*1
  = n-2*2 + 2*2
  = n-3*3 + 3*3
  ...
  = n-sqrt(n)*sqrt(n) + sqrt(n)*sqrt(n)

그렇다면, dp역시 이 관계가 적용되나 생각해보자. 9에서 발생하는 최소 개수를 만들기 위해서는 (8에서 발생하는 최소 개수 + 1에서 발생하는 최소 개수) 그리고 (5에서 발생하는 최소 개수 + 4에서 발생하는 최소 개수), (3에서 발생하는 최소 개수 + 0에서 발생하는 최소 개수)를 비교하면 된다. 이 때 뒤에서 발생하는 최소 개수(1, 4, 0)은 모두 제곱수 이다. 하지만 앞은 제곱수가 아니기 때문에 1보다 큰 숫자를 가지고 있을 것이다. 하지만 업데이트 하는 과정에서 계속해서 숫자가 작아지고, 이것은 문제에서 증명된 사실과 같이 4를 초과할 수 없다. 설명이 너무 어렵다

||0|1|2|3|4|5|6|7|8|9| |::|:|:|:|:|:|:|:|:|:|:| |1|0|1|2|3|1|5|6|7|8|1| |2|0|1|2|3|1|2|3|4|2|1| |3|0|1|2|3|1|2|3|0|0|1| |4|0|1|2|3|1|2|3|0|0|1|

1은 한번의 제곱수까지 사용했을 때 표현할 수 있는지를 나타낸 것이다. 5는 제곱수가 아니므로 초기값을 INF로 잡는다. 그 다음으로 2개의 숫자까지 사용했을 때 필요한 개수를 생각해보자. (1, 4), (2, 3)에서 올 수 있는데, dp값을 더했을 때 최솟값이 2이므로 5는 2개의 제곱수를 사용했을 때 2개를 더하면 만들어진다. 이렇게 모두를 업데이트 하면, 2개의 숫자를 사용했을 때 필요한 제곱수의 최소개수를 업데이트 할 수 있다. 3개의 숫자까지 사용한다면, 여전히 방법을 똑같다. 하지만 이미 dp에 있는 값은 그 숫자를 표현하기 위해 필요한 최소 숫자의 개수를 대변하고 있다. 따라서 업데이트를 하면 자동적으로 최소 개수로 업데이트 된다. 여기서 핵심은 m개의 숫자까지를 사용했을 때 최소숫자의 개수라는 것이다. 즉 열 방향으로도 dp의 정의가 적용되고 있다. 마찬가지로 4번째 숫자까지 사용했을때 업데이트를 진행하면 답이다.

Code

#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
const int INF = 1e9;
int N;
int dp[50001];
 
int main(){
    cin >> N;
    fill(dp, dp+N+1, INF);
    for (int i = 1; i <= N; i++) {
        if (int(sqrt(i))*int(sqrt(i)) == i) dp[i] = 1;
        else dp[i] = i;
    }
    for (int k = 0; k < 3; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= int(sqrt(i)); j++) {
                dp[i] = min(dp[i], dp[j*j]+dp[i-j*j]);
            }
        }
    }
    cout << dp[N] << '\n';
}
 

//
//  main.cpp
//  test
//
//  Created by 최완식 on 2021/03/15.
//
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const int INF = 1e9;
 
int main(){
    int n;
    int dp[50001];
    
    cin >> n;
    fill(dp, dp+n+1, INF);
    
    int i = 1;
    while(true) {
        if (i*i > 50000) {
            break;
        }
        dp[i*i] = 1;
        i++;
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= int(sqrt(i)); j++) {
            dp[i] = min(dp[i], dp[i-j*j] + dp[j*j]);
        }
    }
    cout << dp[n] << endl;
    
    return 0;
}
 

Reference

백준(17626번) - Four Squares{: target=“_blank”}