백준 1699 제곱수의 합

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 어떤수가 제곱수의 합들로 이루어질 때 제곱수의 항의 개수가 가장 적은 경우를 출력하는 문제입니다.

 

저는 이 문제를 bottom - up 방식을 이용하여 반복문을 통하여 해결 하였습니다.

 

dp라는 배열을 선언하고 i라는 숫자에서 i보다 작거나 같은 제곱수를 빼준뒤 기존의 dp[i]에 저장된 값과 비교하여 더작은 값을 넣는 방식입니다.

 

초기 dp[0] 에는 0을 넣어주고 dp[1]에는 1을 넣어주고 시작합니다.

 

dp[i] = min(dp[i], dp[i-j*j] + 1 ) 라는 식이 최종 식입니다.

 

dp[i-j*j] + 1 의 의미는 j*j 제곱수를 사용하여 i를 만드는 경우 입니다. +1 은 j를 사용하였으므로 해주는 것입니다.

 

어떤 제곱수를 사용하느냐에 따라 개수가 달라지므로 가능한 모든 제곱수를 사용하는 경우를 확인해보며 최소의 경우를 저장하고 이후에 그 값들을 이용하는 dp문제입니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <cmath>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N;
	int dp[100001];
	fill_n(dp, 100001, 100000);
	cin >> N;
	dp[0] = 0;
	dp[1] = 1;
	for(int i = 2; i <= 100000; i++) 
		for(int j = 1; j <= (int)sqrt(i); j++) {
			dp[i] = min(dp[i], dp[i-j*j] + 1 ); 
		}
	
	cout<<dp[N];
	return 0;
}