17626 (1) 썸네일형 리스트형 [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 문제 이전 1 다음
