백준 1699 제곱수의 합(C++)

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

1699번: 제곱수의 합

 

문제 유형: DP, Math

 

 

문제 풀이

생각을 했을 때 n이 주어지면, (n - n보다 작은 수 중 가장 큰 제곱 수)의 dp값에서 +1을 해주는 것이 정답이라 생각했다.

그러다 충분히 반례가 존재할거라 생각하여, (n - n보다 작은 수 중 제곱수인 수)의 dp값 + 1 중 가장 작은 것이 정답이라 

생각했다.

1부터 n까지 바텀업 방식으로 dp를 돌린다.

즉, i보다 작은 제곱수를 i에서 뺀 값의 dp에 +1의 가장 작은 값이 dp[i]가 된다.

수식으로 적어보면

dp[i] = min(dp[i - n * n] + 1, dp[i]) 이렇게 된다.

 

전체 코드

#include <iostream>
using namespace std;
int dp[100001];
int main(void)
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n; cin >> n;

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