[백준][C++]17626

늘 그렇든 n=1 부터 구해 보았다.

n	p[n]
1	1
2	2
3	3
4	1
5	2
6	3
7	4
8	2
9	1
10	2
11	3
12	4
13	2
14	3

 

처음에는 n이 제곱수가 되는 시점부터 1234234...를 반복 하는 패턴인 줄 알고 문제를 해결하고 자 하였다.

검증을 위해 예제입력의 결과와 비교해 보니 값이 달랐다.

그러다 다시 생각해 보니. 일단 제곱수인 n들은 무조건 1이 출력되고, 제곱수가 아닌 n 들은 n 보다 작은 제곱수들을 뺀 값에 +1을 하면 되겠다는 걸 알아냈다.

이를 코드로 구현하면

#include<iostream>
#include<vector>
using namespace std;

int main() {
	
	int n; 
	cin >> n;
	
	vector<int>dp(n + 1, 0);
	
	dp[1] = 1;

	for (int i = 2; i <= n; i++) {
		int index= 5; //문제에 4개이하의 제곱수들의 합이라 하여서 최댓값 5로 설정
		for (int j = 1; j * j <= i; j++) {
			
			index = min(index, dp[i - j * j]); //n보다 작은 제곱수들을 각각 비교해서 최솟값을 찾았다.
		}
		dp[i] = index + 1; //index에서 +1을 해주어야 한다 ex) 26= 25^2 + 1^2
	}
	cout << dp[n];
	return 0;
}