Four Squares (feat. 백준, 17626번)

Four Squares
https://www.acmicpc.net/problem/17626

17626번: Four Squares

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <math.h>
using namespace std;
int dp[50001]{0};
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int n;
    cin >> n;
    dp[1] = 1;
    for(register int i = 2, j; i <= n; ++i){
        dp[i] = dp[1] + dp[i - 1];
        for(j = 2; j * j <= i; ++j)
            dp[i] = min(dp[i], 1 + dp[i - j * j]);
    }
    cout << dp[n];
	return 0;
}
// *&)*@*

 

반응형

dp를 이용하는 문제입니다.

dp[100]은 dp[1] + dp[99], dp[2] + dp[98] ... 등으로 표현될 수 있고, 이중 제곱근이 되는 해중 개수가 가장 작은 해를 찾는 문제입니다.