[BOJ 17626] 백준 Four Squares 풀이 - C++

사용언어 :  C++

 

 

 

 

문제풀이

 * dynamic programming 이용하기

* int형 배열인 arr에 값 저장
* 순차적으로 접근
ex) arr[26] 
arr[1]+arr[25], arr[4]+arr[22], arr[9]+arr[15], arr[16]+arr[10], arr[25]+arr[1] 
이 중에서 최솟값이 답이 된다 
여기서 arr[1],arr[4]... 즉, arr[i*i] 꼴은 항상 답은 1이다 (제곱수)
따라서, arr[26-i*i] 중에서 가장 작은 값을 가진 배열이 답이 된다

 

전체코드

 

#include<iostream>
using namespace std;
#include<algorithm>
#define INT_MAX 50005
int n;
int arr[50000];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	
	arr[1] = 1;
	for (int i = 2; i<= n; i++) {
		int tmp = INT_MAX;
		for (int j = 1; j*j <= i; j++) 
			tmp = min(tmp, arr[i - j * j]+1);// 현재 값과 새로 구한 값 중 최솟값으로 수정   
		arr[i] = tmp;//2부터 순서대로 arr배열에 값 저장
	}
    
	cout << arr[n] << "\n";
}

 

 

 

총평

이 문제를 봤을 때, dynamic programming을 이용하면 해결할 수 있는 문제란 건 알 수 있었지만, 그걸 알고 있어도 문제를 풀긴 어려웠다 ㅠㅠ 재귀처럼 아는데도 어려운 부분. 그래도 점점 하다보면 좋아지겄지

 

---

문제 출처

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

17626번: Four Squares