#1699: 제곱수의 합

문제:

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

풀이:

이 문제도 마찬가지로 d 배열에 인덱스 값마다 제곱수들의 합으로 표현시 최소 개수를 저장할 것이다. 예를 들어 1이면 1^2이 하나므로 배열 d[1]에 1을 저장하고 d[2]는 1^2+1^2이므로 2를 저장한다.
이 문제의 핵심은 모든 제곱의 경우의 수를 다 확인 해보는 것이다. 예를 들어 41같은 수는 6^2에서부터 시작하여 41-36을 한뒤 d[5]의 값을 불러오는 것 같지만 5^2을 빼면 16이므로 2번만에 41에 도달 가능하다. 따라서 제일 가까운 제곱값을 찾는 방법으로는 최소 개수를 보장 받을 수 없다.
우선 모든 배열에 최대값인 자기 자신의 값으로 초기화 해준다. 최대값인 이유는 1^2을 자신만큼한게 최대값이기 때문이다. 그 후에는 for문으로 1부터 시작하여 입력값까지 바텀업 방식으로 최소값을 구하면서 올라간다. 두번째 for문에서는 어떤 제곱값이 들어가야 최소값이 나오는지 확인한 뒤 배열에 기록해준다. 우선, 제곱한 값은 현재 확인 중인 값보다 크면 안되므로 j*j ≤ i의 제약을 걸어 놓는다. 그렇게 한 뒤 현재 배열에 저장 된 최소값과 제곱수의 값을 뺀 뒤의 항의 개수를 비교한 뒤 작은 값을 기록한다. 이것을 n까지 반복하면 d[n]에 정답이 저장 되어 있다.

🔍 이제부터 다이나믹 프로그래밍 문제를 풀 때는 배열에 무엇을 저장할 것인지 먼저 생각을 하고 푸는 습관을 들여야겠다. 그리고, 이런 배열에는 보통 답을 조그만한 문제로 쪼개서 하나씩 풀면서 저장을 한 뒤 마지막에 답까지 도달하는 식으로 풀고 이전 값들과 어떤 관계가 있는지도 확인하면 쉽게 풀릴 것 같다.

코드:

#include <iostream>

using namespace std;
	
int n, d[100001];

int main(){
	//입력
	cin >> n;
	//모든 값을 1^2의 합으로 나타냈을 때의 최대 경우의 수로 초기화
	for(int i = 0; i <=n ; i++) d[i] = i;
	//1부터 n까지 하나씩 최소의 경우 수를 저장하면서 바텀업 방식으로 올라간다
	for(int i=1; i<=n ; i++){
		//가능한 제곱의 수 모두 확인
		for(int j=1; j*j <= i; j++){
			//가능한 제곱의 수 확인 후 최소값 저장
			d[i] = min(d[i], d[i-j*j]+1);
		}
	}
	//출력
	cout<<d[n];
}