[DP] BOJ 1699번 제곱수의 합 - 오답노트

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

1699번: 제곱수의 합

- 문제 파악

자연수 N이 주어지면 그 수는 어떠한 제곱수의 합들로 표현할 수 있다. 최소항으로 만들 때 그 개수를 출력하라.

 

- 나의 접근

질문을 뒤져보니 나와 같은 방식으로 많이 접근한 것 같다.

 

일단 주어진 수의 sqrt 한 값을 다시 제곱했을 때 자기 자신일 경우 그 수로 대체하여 계속 1의 제곱을 더해 나가는 것.

하지만 이런식으로 하면 12에서 많이 막히는것 같다.

 

정답) 12 = 2^2 + 2^2 +2^2

오답) 12 = 3^2 + 1^2 +1^2 +1^2

 

- 정답

접근은 유사했으나 12와 같은 예외에 대비해야 한다.

그래서 1부터 주어진수의 sqrt를 취한 값까지 모두 확인해보며 최소값을 찾아야한다.

 

#include "bits/stdc++.h"

using namespace std;

int n;
unsigned long long D[100005];

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

	cin >> n;


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


	cout << D[n];

}