[BOJ 17626] Four Squares

백준 17626

www.acmicpc.net/problem/17626

17626번: Four Squares

1. 주어진 수와 같거나 작은 가장 큰 제곱수를 우선으로 그리디하게 풀면 틀린다.

 

더 작은 경우가 존재

ex) 11339 = 106^2 + 10^2 + 1^2 + 1^2 + 1^2 (5 : 오답)

     11339 = 105^2 + 17^2 + 5^2 (3 : 정답)

 

2. dp를 이용해 min을 갱신하면서 찾는다.

 

dp[n] = 합이 n이 되는 제곱수의 개수라고 하자.

 

 - dp[n] = n이라고 초기화시킬 수 있다. (1^2이 n개 더해진 수)

 - dp[i^2] = 1이다. (어떤 수의 제곱수는 항상 1)

 

 - (중요) dp[n] = dp[n-i] + dp[i]가 성립한다.

 --> dp[n] = dp[n - i^2] + dp[i^2] = dp[n - i^2] + 1

 

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;
	int dp[50001];
	for (int i = 0;i <= 50000;i++) dp[i] = i;
	
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j*j<=i;j++) {
			dp[i] = min(dp[i], 1 + dp[i - j * j]);
		}
	}
	cout << dp[n];
}