[백준 1699] 제곱수의 합

문제 링크 => 1699번: 제곱수의 합 (acmicpc.net)

1699번: 제곱수의 합

---

다이나믹 프로그래밍 문제이다.

 

자연수 N을 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구해야 하는 문제이다.

 

첫번째로 접근한 방법은 다음과 같다.

 

d[1] = 1 / 1개

d[2] = d[1] + d[1] / 2개

d[3] = d[1] + d[1] + d[1] / 3개

d[4] = 4 / 1개

d[5] = d[4] + d[5-4] / 1 + 1 = 2개

d[6] = d[4] + d[6-4] / 1 + 2 = 3개

d[7] = d[4] + d[7-4] / 1 + 3 = 4개

d[8] = d[4] + d[8-4] / 1 + 1 = 2개

d[9] = 9 / 1개

d[10] = d[9] + d[10-9] / 1 + 1 = 2개

d[11] = d[9] + d[11-9] / 1 + 2 = 3개

d[12] = d[9] + d[12-9] / 1 + 3 = 4개

...

 

이런식으로 코드를 제출하였더니 실패가 떳다.

 

반례를 생각해보니 12 에서 문제가 발생하였다.

 

d[12] = d[9] + d[3] => 4개인 반면에,  d[12] = d[4] + d[4] + d[4] = d[4] + d[8] => 3개일수도 있다.

 

또한 d[61] = d[49] + d[12] => 8개인 반면에,   d[61] = d[36] + d[25] => 2개일수도 있다.

 

즉, 위방법에서 구한 d[x] 값과 1~x 사이에 제곱수 y 값과 x-y 값의 제곱수들의 합에 대한 경우도 고려해줘야 한다.

 

즉, for문을 돌려서 d[x] = min(d[x], d[y] + d[x-y]) 값을 할당해주는것이 핵심이다. (y = 1, 4, 9, 16, 25, ... , sqrt(x)*sqrt(x))

 

풀이 code

---

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'

using namespace std;

int d[100001];

void solve(int n) {
	d[1] = 1, d[2] = 2, d[3] = 3;
	for (int i = 2; i <= sqrt(n); i++) {
		d[i * i] = 1;
	}
	int x=4;
	for (int i = 5; i <= n; i++) {
		if (d[i]) {
			x = i;
			continue;
		}
		d[i] = d[x] + d[i - x];
		for (int j = 1; j <= sqrt(i); j++) {
			d[i] = min(d[i], d[j * j] + d[i - j * j]);
		}
	}
	cout << d[n];
}

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

	int n;
	cin >> n;
	solve(n);

	return 0;
}