🖊️ 문제

https://www.acmicpc.net/problem/1699

---

🖊️ 풀이

일단,, 처음에는 while문으로 제곱수를 찾아가며 풀까? 했는데 너무 시간초과 날 것 같았다.

1부터 시작하는 dp로 풀면 될 것 같다.

먼저 쭉~ 풀어보면
n<=3인 경우에는 결과값은 n
제곱수는 무조건 1

dp[1] = 1
dp[2] = 2
dp[3] = 3
dp[4] = 1
dp[5] = dp[4] + dp[1]
dp[6] = dp[4] + dp[2]
dp[7] = dp[4] + dp[3]
dp[8] = dp[4] + dp[4]
dp[9] = 1
dp[10] = dp[9] + dp[1]
dp[11] = dp[9] + dp[2]
..

그래서 마지막 제곱수를 last라고 저장해놓고,
점화식을 다음과 같이 세웠다

if (제곱수라면) 
	dp[i] = sqrt(i)
else
	dp[i] = dp[last] + dp[i - last]

이렇게 풀었더니 틀렸댄다.

왜일까.. 반례가 있었다.

18의 경우,
내 점화식으로 풀게되면
dp[16] + dp[2] = 3의 결과가 나오지만,

dp[9] + dp[9] = 2 이렇게 더 적은 경우의 수가 나올 수 있다..

즉,
직전의 제곱수만 고려하는게 아니라, 모든 제곱수에 대해 고려해봐야 한다.

그래서 제곱수들을 벡터에 모아놓고,
모든 제곱수에 대해서 위 점화식을 통해 계산한 뒤, 최소값을 dp에 저장한다.

단순하게 풀 수 있는 난이도였지만,
반례를 꼭 생각해봐야 하는 문제 ㅠㅠ

실제 코테에서는 이런 히든테케에서 걸리는 경우가 매우! 많기 때문에 반례를 생각하는 연습을 해야 한다!!

#include <iostream>
#include <cmath>
#include <vector>
#include <memory.h>
using namespace std;

int main()
{
	int n;
	cin >> n;

	int result = 0;
	if (n < 4) {
		cout << n << endl;
		return 0;
	}

	int dp[100'001];
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 3;

	vector<int> vec;
	vec.push_back(1);

	int temp = 987654321;
	for (int i = 4; i <= n; i++) {
		if (sqrt(i) - (int)sqrt(i) == 0) {
			dp[i] = 1;
			vec.push_back(i);
		}
		else {
			for (int j = vec.size() - 1; j >= 0; j--) {
				temp = min(temp, dp[vec[j]] + dp[i - vec[j]]);
			}
			dp[i] = temp;
		}
		temp = 987654321;
	}

	cout << dp[n] << endl;
}

`