[BOJ] 백준 17626 Four Squares (Swift)

문제

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

 

풀이

DP로 풀이할 수 있는 문제
$f(1) = 1^2$ 이고, $f(2) = 1^2 + 1^2$로 나타낼 수 있다.

최대 갯수는 $f(n) = f(n - 1) + 1$으로 볼 수 있다.
$f(4) = 2^2$ 같은 경우에는 $2^2$를 어떻게 도출할 수 있을지 생각해보자.

이렇게 생각해보면 되지 않을까?
4는 $2^2$ 이므로, $f(4) = f(4 - 2^2) + 1$

n이 어떤 수의 제곱보다 크거나 같다면 n에서 해당수를 뺀 값에서 +1만큼 경우의 수를 더해주어 n을 만들 수 있다.

$f(n) = min(f(n-1)+1, f(n-i*i)+1$

소스코드

후기

기본적인 DP 문제