1699 제곱수의 합

제곱수의 합 (1699)

 

풀이코드 (탐욕법 오답)

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;
// 1699 제곱수의 합

int n;

// input 의 제곱수들의 합의 최소개수를 반환한다.
int squared(int currentNum){
	// 기저 사례 : input 이 0이면 종료
	if(currentNum == 0)	return 0;
	
	int maxSqrt = (int)sqrt(currentNum);
	
	return squared(currentNum - pow(maxSqrt, 2)) + 1;
}

int main(){

	cin >> n;
	cin.ignore();

	int res = squared(n);
	
	cout << res << endl;
	
}

처음 이 문제에 접근할 때에 항상 최선의 방법을 취하는 탐욕법으로 해결해보았으나 틀렸다. 반례를 찾아보던 중 98 이라는 반례 를 알게되었다. 탐욕법이 최선이 아니라는 것이었다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;
// 1699 제곱수의 합

const int MAX = 100000;
// cache 는 각 수의 제곱수 항의 최소 개수를 갖는다.
int cache[MAX + 1];
int max(int a, int b) {return a < b ? b : a;}
int min(int a, int b) {return a < b ? a : b;}

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

	fill_n(cache, MAX + 1, 317);
	cache[1] = 1;
	for(int i = 2; i <= n; i++){
		if(sqrt(i) - (int)sqrt(i) == 0) {
			cache[i] = 1;
			continue;
		}
		for(int j = 1; j*j <= i; j++){
			cache[i] = min(cache[i], 1 + cache[i - j*j]);
		}
	}
	
	cout << cache[n] << endl;
	
}

해설

---

적용한 레시피 / 방법론 + 접근법

9.21 장의 반복적 동적 계획법이 있다.

반복적 동적 계획법과 재귀적 동적 계획법의 차이를 알고 장단점을 이해하자.

풀이

어떠한 수 k = 제곱수 + (k - 제곱수) 로 표현 될 수 밖에 없다. 그러므로, k 보다 작은 모든 제곱수에 대하여 적용해보고 그 중 가장 min 인 값을 취해보았다.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

- 재귀적으로 구현해보지 못한 것이 아쉽다.

- 또 초기화를 잘못 시켜서 나온 오답이 있었다. dp 문제일 수록 초기화에 신경 써야한다.

- 처음 반복적 동적 계획법을 적용할 때에는 i 가 제곱수가 되었을 때 별다른 조치를 취하지 않았었는데, 오류를 발견하고는 인위적으로 조건문을 넣어서 처리하였다. 조건문 없이 제곱수 까지 처리할 수 있는 방법이 있었을텐데 아쉽다.