[BOJ] 백준 1699번: 제곱수의 합

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

1699번: 제곱수의 합

 

기본적인 DP 문제입니다.

 

#include <bits/stdc++.h>
using namespace std;

int N, dp[100001];

void solve(){
	memset(dp, 0x3f, sizeof(dp));
	dp[0] = 0;
		
	for(int i = 1; i <= N; ++i){
		for(int j = sqrt(i); j >= 1; --j){
			dp[i] = min(dp[i], dp[i-j*j] + 1);		
		}
	}
		
	cout << dp[N];
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N;
	
	solve();
}

 

dp 문제는 항상 1) table 정의 2) 점화식 찾기 3) 초기값 설정의 3단계로 일관성있게 풀이합니다.

 

1) table 정의

dp[i] : i를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수

 

2) 점화식 찾기

for(int i = 1; i <= N; ++i){
    for(int j = sqrt(i); j >= 1; --j){
        dp[i] = min(dp[i], dp[i-j*j] + 1);		
    }
}

3) 초기값 설정

memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;

 

기본적인 DP 예제이지만 좋은 문제들이다보니 여러번 반복해서 풀고 있는데, 새로 풀어 제출할 때마다 예전에 제출한 코드를 다시 확인해 보면 조금씩 구현이 다른 경우가 많습니다. 누군가에게 보여주기 부끄러운 코드들을 볼 때면 이전에 비해 확실히 나아졌다는 성취감을 느끼기도 하고, 종종 과거로부터 배우는 경우도 있습니다.

 

위 코드와 풀이가 이번에 풀었을 때 작성한 것이고 다음 코드는 약 3주 전쯤 작성한 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int N, dp[100001];

void solve(){
	dp[0] = 0;
	for(int i = 1; i <= N; ++i){
		dp[i] = i;
		for(int j = 1; j*j <= i; ++j){
			dp[i] = min(dp[i], dp[i-j*j] + 1);		
		}
	}
		
	cout << dp[N];
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N;
	
	solve();
}

위 코드와 비교했을 때 큰 차이는 없습니다. 시간복잡도도 동일하고 점화식도 동일합니다.

 

단지 반복문을 sqrt 함수를 사용하지 않고 구현한 점, 그리고 자연수 i를 제곱수의 합으로 나타낼 때 그 제곱수의 항의 개수의 최댓값은 i이므로(1^2을 i번 더해서 i를 나타내는 경우) 위 코드와 비교했을 때 가장 타이트한 값으로 초기화한 점이 인상적이었습니다.

 

(이 문제는 test case가 한 가지이고 전역변수로 정수 자료형의 배열을 선언할 경우 값이 0으로 초기화되므로 두 번째 코드의 solve 함수 내에 dp[0] = 0은 사실 불필요하지만 알고리즘을 명확하게 하기 위해 명시했습니다.)

 

두 코드 모두 시간복잡도는 O(N^1.5)입니다.