(C++) - 백준(BOJ) 17626번 : Four Squares 답

www.acmicpc.net/problem/17626

17626번: Four Squares

dp문제였습니다.

 

풀이방법

 i라는 제곱수를 구하기 위해 필요한 최소 숫자의 개수는 min(dp[i], j = 1부터 루트 i까지 dp[j*j] + dp[i-j*j]) 입니다.

 

Code

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int n;
vector <int> dp (50001,0x7f7f7f7f);

int main(){
    cin >> n;
    for(int i  =1; i<=n; i++){
        if((int)sqrt(i) * (int)sqrt(i)==i) dp[i] = 1;
    }
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= (int)sqrt(i); j++){
            dp[i] = min(dp[i],dp[j*j] + dp[i-j*j]);
        }
    }
    cout << dp[n];
}