[C++] 백준 17626 Four Squares

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

17626번: Four Squares

풀이

임의의 자연수를 만드는데 필요한 제곱수의 최소 개수를 저장하는 DP를 사용해 풀이하면 된다.

1. 모든 자연수는 넷 혹은 그 이하의 제곱수 합으로 표현할 수 있다.

2. 예시

 n       1 2 3 4 5 6 7 8 을 표현하면

dp[n]  1 2 3 1 2 3 4 2 

이다. 

3. 임의의 자연수에서 제곱수를 뺏을 때, dp[n]이 최소값을 가지는 숫자에서 해당 자연수를 만들면 된다.

즉, 7에서 제곱수 1과 4를 뺀 6, 3에서 7을 만들 수 있고, 두 수 모두 dp[n]=3 이므로 dp[7]=dp[6]+1 이다.

4. dp[4] 의 경우 min(dp[3], dp[0]) = dp[0] = 0 이다. 따라서 dp[4]=dp[0]+1

5. dp[n] = min(dp[n-1^2], dp[n-2^2], .... dp[n-i^2]) + 1 임을 기억하자.

 

 

#include <iostream>
#include <vector>

using namespace std;

int n, k, ans=2147000000;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    // freopen("input.txt", "r", stdin);
    
    cin >> n;
    vector<int> dp(n+1, 0);
    dp[1]=1;

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

    return 0;
}