이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 56 번째 글 입니다.
목차
실버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;
}