백준 17626번, Four Squares

백준 17626번 c++ 문제풀이

문제:

백준 17626

풀이:

1. dp[i]를 i에 대해 최소개수라고 설정한다.
2. dp[i] = dp[a] + dp[i+b]를 만족한다.
3. 예를 들어.
   dp[5] = dp[1] + dp[4]
   dp[5] = dp[2] + dp[3]
   .
   .
   이런 식으로 표현할 수 있다.
4. 위의 예시처럼 여러가지로 표현할 수 있는데 그 중 최솟값을 찾으면 된다.
5. 따라서 dp[input]의 점화식은 dp[input] = dp[ii] + dp[n-ii]

코드:

#include <iostream>
#include <algorithm>

using namespace std;

int dp[50001];

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int input;

    cin >> input;

    for(int i=1;i*i<=input;i++){  //input이 딱 제곱수 이면 한개.
        dp[i*i] = 1;
    }

    for(int i=1;i<=input;i++){
        if(dp[i] != 0){
            continue;
        }else{
            for(int j=1;j*j<=i;j++){
                if(dp[i] == 0){
                    dp[i] = dp[j*j] + dp[i - j*j];  //dp[i] == 0일떄 점화식을 통해 저장해주고, 밑의 min함수를 통해 그값을 최솟값으로 갱신해준다.
                }
                else{
                    dp[i] = min(dp[i], dp[j*j] + dp[i-j*j]);
                }
            }
        }
    }

    cout << dp[input] <<"\n";

    return 0;
} 

dp[i*i] = 1로 미리 정해주고, 1~input까지 dp[i] 중 값이 0인 것들을 위의 점화식을 적용해준다. 그리고 그 중 가장 작은 값을 저장한다.

감사합니다.