[c++] 백준 17626: Four Squares

문제 링크
https://www.acmicpc.net/problem/17626

이 문제는 9달 전에 풀었는데, 어느순간 와서 보니 오답 처리가 되어었던 문제다.

오답 코드를 보자

오답 코드

#include <iostream>
#include <algorithm>
#include <limits.h>
#include <cmath>

#define FIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)

using namespace std;

int nn[224];
int n;
int sq_n;
int m = 4;
void f(int sum, int idx, int cnt) {

	if (sum == n) {
		if (cnt < m) m = cnt;
		return;
	}
	
	if (nn[idx] > n || cnt >= 4) return; // <-- 이 부분 의심!!
	

	f(sum + nn[idx], idx + 1, cnt + 1);
	f(sum, idx + 1, cnt);
}

int main()
{
	FIO;
	for (int i = 1; i <224; i++) {
		nn[i] = i * i;
	}
	cin >> n;
	//sq_n = (int)sqrt(n);
	
	f(0,1,0);
	cout << m;
}

음... 일단 한눈에 봐도 시간초과가 날 것 같은 코드다.
오답 처리가 의심되는 부분을 체크해보았다. 숫자를 5로 바꿔보니 아니나 다를까 시간초과가 나왔다.
시간 복잡도는 O(2^(루트N))로 대략 2^224 = 2.6959947e+67 번정도 계산...

풀이

dp를 생각해볼 수 있다.
i를 2부터 n까지 증가시키면서
dp[i] = min(dp[i], dp[j*j] + dp[i- j*j])
하면 정답

#include <iostream>
#include <algorithm>
#include <limits.h>
#include <cmath>

#define FIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)

using namespace std;

int n;
int dp[50001];
int main()
{
	dp[1] = 1;
	FIO;
	cin >> n;
	for (int i = 2; i <= n; i++) {
		dp[i] = 1 + dp[i - 1]; // 전에 것에다가 +1 해주는 경우, 초기값 설정이라 생각
		for (int j = 2; j * j <= i; j++) dp[i] = min(dp[i], 1 + dp[i - j * j]);
     		// 							== dp[j*j] + dp[i-j*j] 
	}
	cout << dp[n];

}