BOJ 1699번 제곱수의 합

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

GitHub : https://github.com/junho0956/Algorithm/blob/master/1699/1699/%EC%86%8C%EC%8A%A4.cpp

 

 

1부터 N까지 모두 제곱수의 합으로 나타낼 수 있다.

 

먼저 dp[i]는 i를 제곱수의 합으로 나타내는 경우라고 할 때

1로 i를 구성한다면 기본 갯수는 i가 된다.

 

그리고 1부터 시작해서 어떤 수를 제곱했을 때 i에 가장 가까운 수를 k*k이라고 했을 때

점화식은 dp[i]=min(dp[i],dp[i-k*k]+1) 이 될 것이다.

 

ex) dp[4]의 경우

dp[4] = min(dp[4], dp[4-1*1]+1) <= 현재 dp[4] 는 4, dp[4-1*1] + 1 => dp[3]+1 = 4 같음

dp[4] = min(dp[4], dp[4-2*2]+1) <= 현재 dp[4] 는 4, dp[4-2*2] + 1 => dp[0]+1 = 1 갱신

 

 

 

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

 

 

복습 20.02.09 재귀로 해결!

그런데 시간차이가 심하다. .. ...