문제
https://www.acmicpc.net/problem/17626
https://www.acmicpc.net/problem/1699
문제해설
두 문제가 같은 문제여서 풀이를 한번만 쓴다.
어떤 자연수의 합을 제곱수로 표현하는 문제이다.
자연수 n이 주어지고 최소 몇 개의 제곱수로 n을 표현할 수 있는지 찾으면 된다.
문제풀이
처음에 풀 때는
단순히 가장 큰 제곱수를 뺀 dp값이 답이라고 생각했다.
예를 들어 11이라는 수가 주어진다면
가장 큰 제곱수는 9이다.
11 - 9 = 2이고 dp[2] + 1이 최소일거라 생각했다.
하지만 23같은 경우는
16 + 4 + 1 + 1 + 1 보다
9 + 9 + 4 + 1이 더 작다. 그러므로 위의 방법은 틀렸다.
이 문제는 탐색의 과정도 필요하다.
아까 23을 다시 살펴보자
23보다 작은 제곱수들을 다 보는 것이다.
1, 4, 9, 16이 있으면 23에서 해당 값들을 뺀 값인
dp[22], dp[19], dp[14], dp[7] 중에서
가장 작은 값에 +1을 해준 값이 dp[23]이 된다.
예를들어 dp[7]를 골랐다면
23은 16 + 4 + 1 + 1 + 1로 5가 되는 것이고
dp[22]를 골랐다면 9 + 9 + 4 + 1로 4가 되는 것이다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<algorithm>
#include<vector>
#include<limits.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n; cin >> n;
vector<int>dp(n + 1, 0);
dp[1] = 1;
for (int i = 2; i <= n; i++) {
int minn = INT_MAX;
for (int j = 1; j * j <= i; j++) {
int tmp = i - j * j;
minn = min(minn, dp[tmp]);
}
dp[i] = minn + 1;
}
cout << dp[n];
return 0;
}