백준 제곱수의 합 [c++]

1699 제곱수의 합 실버 2

문제 링크

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	59480	24194	17654	39.769%

문제

어떤 자연수 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)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

풀이

처음에는 BFS로 해결하려 했다. 테스트케이스는 모두 맞았지만, 틀렸다.
메모리 초과로 문제 조건을 보니 128MB이다.
풀이를 찾아보니 DP로 해결 할 수 있었다.

점화식은 다음과 같다.

dp[n]=min(dp[n], dp[n-ii]+1), (1<= ii <= n)

n이 1일 때 : 1^2 n이 2일 때 : 1^2 + 1^2 n이 3일 때 : 1^2 + 1^2 + 1^2

n이 4일 때 : 2^2 인데 이는

dp[4 - 1*1] = dp[3] = 3

dp[4 - 2*2] = dp[0] = 0

점화식에 의해 min(3,0+1)중 최소인 1이 선택됨.

마찬가지 11일때도 : 3^2 + 1^2 + 1^2

dp[11 - 1*1] = dp[10] = 2

dp[11 - 2*2] = dp[7] = 4

dp[11 - 3*3] = dp[2] = 2

점화식에 의해 min(11,2+1,4+1, 2+1) 중 최소인 3이 선택.

코드

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin >> n;
    
    int dp[100001];
    for(int i = 0; i < 100001; i++)
    {
        dp[i] = i;
    }

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

    cout << dp[n] << endl;

    return 0;
}

• ps
• dp