[DP] 백준 1699 제곱수의 합 C++

 

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

1699번: 제곱수의 합

---

---

풀이 :

 간단한 문제자체는 간단한데 나만 어려웠나..? 생각보다 잘 안풀렸다. 솔루션 자체는 간단한데 생각보다 제곱수 빼고 하는 걸 구현하는데 삽질을 좀 했다. 해결하는 아이디어 자체는 조금 생각해보면 금방 떠올릴 수 있는 정도 내가 어려웠던 점은 반복문 한번으로 구할 수 있을 것 같아서 고민하다가 결국 솔루션을 봤는데 이중 반복문으로 j * j <= i 이런식으로 제곱수의 근사값까지 계산하는 걸 생각못했다.. 솔루션을 좀 풀어서 설명해보자면

 

dp[n] = a 일때 숫자 n을 제곱수의 합으로 나타낼 때 제곱항의 최소숫자를 a로 생각한다.

dp[1]은 당연히 1이고

dp[2] = 2 (1의 제곱 2개)

dp[3] = 3 (1의 제곱 3개)

 

dp[4] 부터는 제곱수를 고려해줘야 한다. 2의 제곱 은 4이기 때문에 dp[4] =1

dp[5]=2 인데 제곱수인 4 + 1 = 5 이기 때문

즉, n보다 작은 제곱수의 근사값을 고려해줘야 한다. 반복문 돌면서 dp[i - j*j]+1 하면 되는데 좀 더 큰 수로 예를 들자면

 

16 같은 경우는 내부 반복문의 j 가 1, 2, 3, 4 이렇게 네번 돌면서 이전에 저장해온 dp 값을 계속 비교하며 최소값을 저장해주면 됨

 

코드 :

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

int dp[100001];
int N;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	for (int i = 1; i <= N; i++) {
		dp[i] = i;
		for (int j = 1; j *j <= i; j++) {
			dp[i] = min(dp[i], dp[i - j * j] + 1);
		}
	}
	

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