[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$

소스코드

	let n = Int(readLine()!)!
	var dp = [Int](repeating: 0, count: 50_001)
	dp[1] = 1
	for i in 2...50000 {
	dp[i] = dp[i - 1] + 1
	var j = 1
	while i - j * j >= 0 {
	dp[i] = min(dp[i], dp[i - j * j] + 1)
	j += 1
	}
	}
	print(dp[n])

view raw Four Squares.swift hosted with ❤ by GitHub

후기

기본적인 DP 문제