자주 보이는 dp 유형 중 하나 근데 풀 때마다 막막하다...
점화식을 세우기 위해 숫자 하나씩 해본다.
1 = 1 * 1
2 = 1 * 1 + 1 * 1
3 = 1 * 1 + 1 * 1 + 1 * 1
4 = 2 * 2
5 = 2 * 2 + 1 * 1
....
10 = 3 * 3 + 1
dp[n]은 제곱수 합으로 표현할 때 사용하는 숫자의 최소 개수라고 정의한다.
그러면 n이 제곱이면 dp[n] = 1이다.
n이 제곱이 아니라면 dp[n] = dp[n-i*i] + dp[i*i]이다. 이때 i는 i*i<=n이며 dp[i*i]= 1이므로
dp[n] = dp[n - i*i] + 1 이다.
첫 번째 실수:
i를 n에 가장 가까운 수라고 정의함(예를 들면 10에선 9만 고려함.. 4도 고려해야 한다) 가장 가깝다고 dp[n]이 최소가 되는 것이 아니기 때문에 i*i<=n인 모든 경우의 수를 따져줘야 한다.
성공한 첫 번째 코드 16ms소요
#include <stdio.h>
#include <algorithm>
#include <limits.h>
using namespace std;
int arr[50001];
int main(void)
{
int n;
scanf("%d", &n);
arr[0] = 1;
for (int i = 1; i <= n; i++)
{
arr[i] = INT_MAX;
}
for (int i = 1; i * i <= n; i++)
{
arr[i * i] = 1;
}
for (int i = 2; i <= n; i++)
{
if (arr[i] == 1)
continue;
for (int j = 1; j * j < i; j++)
{
arr[i] = min(arr[i], arr[i - j * j] + arr[j * j]);
}
}
printf("%d\n", arr[n]);
return 0;
}
시간이 긴거 같아 다른 사람코드 보고 더 짧게 고쳐봤다. 8ms소요
#include <stdio.h>
#include <algorithm>
using namespace std;
int arr[50001];
int main(void)
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
arr[i] = i;
}
for (int i = 1; i * i <= n; i++)
{
for (int j = i * i; j <= n; j++)
{
arr[j] = min(arr[j], arr[j - i * i] + 1);
}
}
printf("%d\n", arr[n]);
return 0;
}
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
[백준 15486] 퇴사 2 (0) | 2020.11.26 |
---|---|
[백준 19947] 투자의 귀재 배주형 (0) | 2020.11.26 |
[백준 2503] 숫자 야구 (0) | 2020.11.26 |
[백준 5639] 이진검색트리 (0) | 2020.11.24 |
[백준 16945] 매직 스퀘어로 변경하기 (0) | 2020.11.23 |
댓글