(백준 1699번 제곱수의 합 C++) 라이님 블로그 대회 알고리즘 따라잡기 5) DP(Dynamic Programming) 동적계획법 5

DPDP딥이 아침에 잘 풀려서 두 문제를 풀고 출근하려고 한다!

 

백준 1699번

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

1699번: 제곱수의 합

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAX_N = 100001;
int N, DP[MAX_N]; 

int f(int n) {
	if (DP[n] != -1) return DP[n];
	int result = n;
	int root_n = floor(sqrt(n));
	for (int i = 1; i <= root_n; i++) {
		result = min(result, f(n - i * i) + 1);
	}
	DP[n] = result;
	return result;
}

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N + 1; i++) DP[i] = -1;
	
	int ans = f(N);
	printf("%d", ans);
	return 0;

}

 

어제도 같은 방법으로 짰던 것 같은데, 역시 아침이 머리가 맑아서 그런가ㅎㅎ 잘 풀려서 좋다. 

어제 짠 코드를 보니 아래와 같은데, 

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAX_N = 100001;
int N, dp[MAX_N];

int f(int n) {
	if (n == 1) return 1;
	if (n == 2) return 2;
	if (n == 3) return 3;
	if (dp[n] != -1) dp[n];
	int root_n = floor(sqrt(n));
	int result = n;
	for (int i = 1; i < root_n+1; i++)
		result = min(result, f(n - i * i) + 1);
	dp[n] = result;
	return result;
}

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N+1; i++) dp[i] = -1;
	dp[0] = 0, dp[1] = 1, dp[2] = 2, dp[3] = 3;
	int ans = f(N);
	printf("%d", ans);
	return 0;
}

 

다른 점은 n == 1, 2, 3일 때를 check한다는 점..? 연산량이 3만큼 늘어나는데 dp[n]을 계산하기 위해 $sqrt{n}$의 for loop을 돌고, dp[$sqrt{n}$]을 계산하기 위해 $sqrt{sqrt{n}}$의 for loop을 돌고,,, 

그러면 $n^{\frac{1}{2} + \frac{1}{4}+...} = n$번의 for loop을 돌게 되고, 이때마다 3번의 연산을 더 하므로 최대 3 * 10^5의 연산을 더 하게 된다.. 는게 내 생각인데, 1초라는 시간이면 1억번의 연산이 가능하고, 30만번은 괜찮을 것 같은데 시간 초과가 나서 뭔가,, 이해가 안된다.

 

누가 이거 보면 설명 좀 부탁드립니다..

지나가던 재야의 고수님들..