[C++] BOJ-1699

 

 

문제풀이

---

1. cache배열의 인덱스 값을 제곱수로 생각하고 점화식을 구현하였다.

cache[j] = min(cache[j], cache[j-dp_pow(i)]+1)

 

2. 전체 소스

 

#include <iostream>

using namespace std;

int dp_pow(int a){
	return a*a;
}

int main(){
	ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int N;
	
	cin >> N;
	int cache[N+1] = {};
	

	for(int i = 1; i<=N; i++){
		cache[i] = 987654321;
	}
	
	for(int i = 1; dp_pow(i) <= N; i++){
		for(int j = dp_pow(i); j<=N; j++){
			cache[j] = min(cache[j], cache[j-dp_pow(i)]+1);
		}
	}
	
	
	cout << cache[N];
}