[백준] 17626번 Four Squares C++ 문제풀이

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

17626번: Four Squares

문제 풀이

그 전에 풀었던 문제가 그리디 문제여서 이번 문제도 별 생각 없이 그리디로 접근했다가 예제는 잘 나왔는데 틀렸다.

제곱수들의 배열을 만들고 n보다 작고, 가장 가까운 제곱수를 만나면 빼고 다시 n보다 작고, 가장 가까운 제곱수 찾아서~~ 이런식으로 구현했다.

이 경우 n = 21841이면 21841 = 104 ^ 2 + 105 ^ 2이 최적인데 나는  147 * 147 = 21609라 그리디는 최적의 경우를 보장하지 않더라...

결론적으로 DP를 이용해 문제를 해결했다.

num[n] = min(num[n] , num[n-1^2) +1,  num[n-2^2] +1 ...) 이런식으로 구현했다.

소스 코드

#include <iostream>
using namespace std;

int square_num[50001] = { 0 };

int main() {
	int n;
	cin >> n;
	// 초기화
	for (int i = 0; i <= n; i++) {
		square_num[i] = 99999999;
	}
	for (int i = 0; i * i <= n; i++) {
		square_num[i * i] = 1;
	}
    
	//dp를 이용한 최소횟수 구하기
	for (int i = 2; i <= n; i++) {
		for (int j = 1; i - j * j >= 0; j++) {
			square_num[i] = min(square_num[i], square_num[i - j * j] + 1);
		}
	}
	cout << square_num[n] << '\n';
}