[알고리즘] 백준 17626번: Four Squares (C++), 오래간만에 DP 포스팅

오래간만에 DP문제를 풀었다. 이번 문제는 점화식이 꽤 어렵지 않았다. 하지만, 틀린 점화식이었다.

작성했던 코드는 이랬다.

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

int cache[50001] = { 0, };

int main() {
	int n;
	cin >> n;
	cache[1] = 1;
	cache[2] = 2;
	cache[3] = 3;
	int num = 2;
	for (int i = 4; i <= n; i++) {
		if (i % (num * num) == 0) {
			cache[i] = 1;
			num++;
		}
		else {
			cache[i] = cache[i - 1] + 1;
		}
	}

	cout << cache[n];
	return 0;
}

---

두 가지 문제

이럴 경우 두 가지의 문제가 발생한다. 여러 가지 제곱수가 들어가지 못하는 점

예를 들어, 8이면 2^2 + 2^2 형태로 나타내는데 2^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2의 형태로 밖에 나타내지 못한다.

그리고, 12의 경우 뺄 수 있는 값 중 가장 큰 값인 9(3^2)의 값이 빠져나가면 1^2이 3번 더해져 12의 값을 인풋으로 넣으면 4가 리턴된다. 하지만, 이는 그리디 알고리즘 같은 해결 방법에다가 이는 최적의 해가 아니다. 12의 경우 2^2를 3번 더하면 12가 완성된다. 즉, 12가 가질 수 있는 최적의 해는 3이다. 

---

포인트

이 문제는 12 같은 경우를 면하기 위해 모든 경우의 수를 다 세어보고, 그중에 최솟값을 구해야 한다. 그런 의미에서 알고리즘 분류를 보면 브루트 포스 알고리즘이라고 되어있다. 

 

그렇게 되어서 나올 수 있는 코드는 이랬다.

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

int cache[50001] = { 0, };

int main() {
	int n;
	cin >> n;
	cache[1] = 1;

	for (int i = 1; i <= n; i++) {
		cache[i] = cache[1] + cache[i - 1];
		for (int j = 2; j * j <= i; j++) {
			cache[i] = min(cache[i], 1 + cache[i - j * j]);
		}
	}

	cout << cache[n];
	return 0;
}

cache[i] = cache[1] + cache[i - 1]의 뜻은 기존의 값에서 1의 제곱을 더해서도 그 값을 구할 수 있기 때문에 하나의 경우의 수로 처리해주었다. 그다음부터 for문은 어떤 제곱수를 늘려가면서 예를 들어, 10이라면

cache[4] + cache[6]

cache[9] + cache[1]

의 형태로 나타내가며 1 + cache[i - j * j]의 코드에서 1을 더해주는 값이 제곱수를 나타내는 것을 알 수 있다.

min 함수를 통해 최솟값을 도출해낸다.

---

느낀 점

여전히 점화식의 접근이 어려웠다. 더군다나 이번 문제는 DP로 풀어야 하는데 나도 모르게 무의식적으로 그리디 알고리즘으로 풀려했었던 걸 보면 아직 이쪽 부분은 내가 논리력이 많이 부족하구나를 깨닫는다. 점화식, 즉 관계식에 대해 많은 공부를 해야 한다.