백준 1699 제곱수의 합(dynamic programming)

#include <iostream>



using namespace std;

const int MAX = 100000;

int N;

int cache[MAX];



void minSquare()

{

    for (int i = 0; i <= N; i++)

        cache[i] = i;

    for (int i = 2; i <= N; i++)

    {

        for (int j = 2; j * j <= i; j++)

            cache[i] = min(cache[i], cache[i - j * j] + 1);

    }

    cout << cache[N];

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(NULL);

    cin >> N;

    minSquare();

}

개인적으로 많이 어려웠다...

 

   cache[i] = min(cache[i], cache[i - j * j] + 1); 이 점화식을 알아내는데 애를 먹었는데 확실히 dp문제들은 수학적 사고가 있어야 쉽게 풀 수 있는 것 같다.

 

이런 점화식이 나오는 이유는 만약 cache[15]를 구한다고 하자. 이 값의 최소는 결국 cache[15-1]+1, cache[15-2^2]+1, cache[15-3^3]+1 중 최소값이 될 것이다. +1을 하는 이유는 제곱수 연산 한번이 더해져야 할 것이기 때문이다.

 

for loop의 시작이 2인 이유는 어짜피 1일 때는 1을 가지기 때문이다.

 

점점 감을 잡아가는 것 같으면서도 아직 많이 어렵다... 그래도 점화식을 도출하는데 조금씩 익숙해지는 것 같아 다행이다.