백준, BOJ, 1699번, 제곱수의 합 : C++ [CPP]

처음부터 생각하기는 힘들다.

DP라는 것을 예상할 수 있지만 점화식을 바로 생각하기는 어렵다.

 

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

 

---

 

#맞는 풀이

#include <iostream>
#include <algorithm>

using namespace std;

// 100000을 루트하면 대충 350 이하..

//또한 최소항의 수를 만들기 위해 큰 것부터 집어넣기로함, 그리드
// 그리드로 안풀림..ㅎ dp로 풀어야할 듯.

int arr[100001];
int N;


int main(){
    cin >> N;
    //모든 N에 대해서 최소항의 개수를 찾아봄
    for(int i = 1; i<=N; i++){
        arr[i] = i;
        //i에 대해서 i보다 작거나 같은 제곱수를 모두 빼본다.
        // -> 어떤 제곱수 항을 가져야 최소 개수를 가질지 다 뒤져봄
        // -> 그리디는 틀린 방식  18 = 4^2,1^2,1^2 지만 사실 3^2,3^2가 더 최소항임.
        for(int j = 1; j*j<=i; j++){
            arr[i] = min(arr[i], arr[i-j*j]+1);
        }
    }
    
    cout <<arr[N];
}