[백준] 17626번

이것도 DP 문제다.

전에 감을 잡은 듯 했지만, 아직 감을 잡지 못한듯하다.

 

그니까 최소로 만들 수 있는 횟수를 고려하고 이를 적용하면 쉽게 문제를 풀 수 있는 듯하다.

#include <iostream>
#include <cmath>
#include <vector>


int main() {
    int n;
    std::cin >> n;
    std::vector<int> arr(n+1,4);
    arr[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j *j <= i; j++) {
            arr[i] = std::min(arr[i], arr[i-j*j]+1);
        }
        // std::cout << i <<" : "<<arr[i] <<std::endl;
    }

    std::cout << arr[n];

}