백준 17626번 c++ 풀이

안녕하세요 오늘은 다이나믹 프로그래밍 및 브루트 포스를 이용한 문제를 풀어보도록 하겠습니다.

 

전략:

1. 범위가 50000까지이니까 길이 50001짜리 배열을 만들어서 동적 계획법을 이용할 준비를 한다. sq라는 함수를 이용하여 재귀를 구현할거다.

2. 만약 arr[a]가 존재를 하면, arr[a]를 return해줍니다. 그것이 아니면 arr[a]의 값을 집어넣어줘야하는데, 만약 a의 제곱근을 제곱한 값이 a와 같다면 arr[a]에 1을 대입해주고, 1을 반환해준다.

3. 그렇지 않다면 count라는 변수를 만들어서 1(arr[i*i]) + sq(a-temp)를 대입해준다. 그리고 min와 비교하여 더 작은 값을 min에 대입해준다. for문이 끝났을 때 min값을 arr[a]에 대입해준다.

 

코드:

#include <bits/stdc++.h>
using namespace std;
int arr[50001];
int sq(int a){
	if(arr[a]){
		return arr[a];
	}
	else{
		int min = 50000;
		int temp, count;
		int x = sqrt(a);
		if(x * x == a){
			arr[a] = 1;
			return 1;
		}
		for(int i= 1; i<=sqrt(a); ++i){
			temp = i*i;
			count = 1 + sq(a-temp);
			if(min>count){
				min = count;
			}
		}
		arr[a] = min;
		return min;
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N;
	cin>>N;
	cout<<sq(N)<<"\n";
	
}