백준 1699 - 제곱수의 합

문제

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

1699번: 제곱수의 합

 

풀이

어떤 수를 제곱수들로 표현을 할 때 , 무조건 큰 수의 의 제곱수들로만 나타내는 것은 답이 아니다. 예를 들어 

43 = 25+9+9 < 36+4+1+1+1 이 된다.

 

43을 표현하기 위해서는 일단 43 전 까지의 제곱수 들이 필요하다. 1, 4, 9, 16, 25, 36이 있다. 이 수들을 이용해서 최소 합의 수를 구하는 방법은 다시 6가지 경우로 나누어 진다. 43 - 1, 43 - 4, 43 - 9, 43 - 16, 43 - 25, 43 - 36 이렇게 나누어서 어떤 경우가 최소가 되는지를 알아야 한다.

 

이를 바탕으로 다음과 같은 식을 세울 수 있다.

dp[43] = min {

dp[43 - 1*1] = dp[42] = 36 + 4 + 1 + 1 = 4,

dp[43 - 2*2] = dp[39] = 36 + 1 + 1 + 1 = 4,

dp[43 - 3*3] = dp[34] = 25 + 9 = 2,

dp[43 - 4*4] = dp[27] = 25 + 1 + 1 = 3,

dp[43 - 5*5] = dp[18] = 16 + 1 + 1 = 3,

dp[43 - 6* 6] = dp[7] = 4 + 1 + 1 + 1 = 4

} + 1 (1을 더하는 이유는 제곱수를 실제로 사용해서 빼기 때문)

 

결국 dp[43] = 3이 된다.

 

코드

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int N;
int dp[100001];
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> N;
 
    for (int i = 1; i <= N; i++) dp[i] = i;
 
    for (int i = 2; i <= N; i++)
        for (int j = 2; j*j <= i; j++)
            dp[i] = min(dp[i], dp[i - j * j] + 1);
 
    cout << dp[N];
 
    return 0;
}
 

 

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int N;
int dp[317][100001];
 
int f(int k, int N)
{
    if (k == 0) return (N == 0 ? 0 : 100001);
    if (dp[k][N]) return dp[k][N];
 
    int result = f(k - 1, N);
    if (N >= k*k) result = min(result, f(k, N - (k*k)) + 1);
    dp[k][N] = result;
 
    return result;
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> N;
 
    int start;
    for (start = 1; start*start <= N; start++);
    start--;
 
    cout << f(start, N);
 
 
    return 0;
}
 

동전 2 문제와 같은 원리로 해결한 방법이다. N 이전에 제곱수 들을 이용하고 f(k, N) 함수를 이용한다.

f(k, N) = k의 제곱수 부터 이용해서 N을 구하는 최소의 수