[BOJ 1699] 백준 제곱수의 합 풀이 - C++

사용언어 :  C++

 

 

 

 

 

문제풀이

 * dynamic programming 이용하기

자세한 풀이 : https://developing-soosoo.tistory.com/32

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

 

 

전체코드

 

#include<iostream>
#include<algorithm>
using namespace std;
int N;
int arr[100001];
int main() {
	cin >> N;

	arr[1] = 1;
	int i = 0;
	for ( i = 2; i <= N; i++) {
		int tmp = 100000;
		for (int j = 1; j*j <= i; j++) {
			tmp = min(tmp, arr[i - j * j] + 1);
		}
		arr[i] = tmp;
	}
	cout << arr[N];
}

 

 

 

총평

거의 같은 문제인 four squares를 풀자마자 풀어서 어려움 없이 풀 수 있었다

 

---

문제 출처

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

1699번: 제곱수의 합