https://www.acmicpc.net/problem/1699
문제
> 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다.
> 예를 들어 11=3^2+1^2+1^2(3개 항)이다.
> 이런 표현방법은 여러 가지가 될 수 있는데,
11의 경우 11=2^2+2^2+1^2+1^2+1^2(5개 항)도 가능하다.
> 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다.
> 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로,
11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.
> 주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.접근
DP를 사용해서 작은 수들의 항의 개수를 이용해 큰수를 구한다.
dp(i)를 각 i에 대해 가능한 최소의 항이라고 하면 일단 최악의 경우의 수는 전부 1의 제곱을 나타냈을 때이다.
1부터 3까지는 1의 제곱들 밖에못오고 4부터는 2의 제곱이 올 수 있기 때문에 4부터 따져준다.
4보다 작은 수 중 제곱해서 4가 되거나 4보다 작으면 그 수를 항으로 가지고 (항 개수 +1), 4에서 그수의 제곱을 뺀수의 dp값을 더해주면 된다.
예를 들어 i를 7이라고 한다면 1의 제곱부터 쭉 왔을 때 7보다 작거나같은 수 중 될 수 있는 경우는 1과 2이다. 그래서
dp(7)과, dp(7-(1^2))+1 중 더 작은 거를 고르고,
또 2도 가능하니까 위의 결과 중 더 작은것과
dp(7-(2^2)+1)한 것 중 더 작은걸 고르면 해당 수의 최소 항의 개수를 구할 수 있다. 각각 dp(6)+1과 dp(3)+1에서의 dp값들은 이미 올라오면서 각각의 최소항의 개수를 구하고 온 애들이니까 이다.
문제해결
> 0부터 입렵받은 수 까지 dp(N)의 값을 최악의 경우로 초기화 해준다.
> 3까진 최악의 경우가 최소값이므로 4부터 따져준다.
> 1부터 제곱해서 i보다 작은 수 까지만 경우로 따지며, 각각
i에서 제곱한 수를뺀 dp값+1(제곱해서 뺀 수가 한 항으로 쳐지므로)를 서로 비교해 더 작은 수를 골라낸다.
> N의 dp값을 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
vector<int> dp(N+1);
for (int i = 0; i <= N; i++) dp[i] = i;
for (int i = 4; i <= N; i++)
{
for (int j = 1; j * j <= i; j++)
{
dp[i] = min(dp[i], dp[i - j * j] + 1);
}
}
cout << dp[N] << '\n';
}
후기
처음에 그냥 while문으로 입력받은 수의 sqrt값을 정수로 변환하여 뺀다음, 또 그수의 sqrt의 정수형을 빼는걸 반복하며 0이 나올 때까지 했다.
이렇게 했더니 틀려서 반례를 생각했는데 12가 들어온다면
내 방식으론 3^2+1^2+1^2+1^2으로 총 4개가 나온다. 하지만
최소의 경우는 2^2+2^2+2^2으로 3가지이다.
그래서 특정 수의 제곱이 입력받은 수보다 작은 즉 가능한 제곱수를 모두 따져주는 현 방법으로 해서 맞았다.
