[BaekJoon] 백준 17626번 : Four Squares

17626번 : Four Squares

DP 와 브루트포스를 이용하면 되는 문제이다.

num = 1 + dp[pivot^2 - num] 을 통해 구할 수 있다. pivot 은 1부터 pivot**2 가 num 이하 일 때 까지 1씩 증가한다.

만약 32를 구하고 싶은 경우

1 + dp[31]

1 + dp[28]

1 + dp[23]

1 + dp[16]

1 + dp[7] 를 계산해 가장 작은 값을 dp[32] 에 넣어주면 된다.

---

def solution(num):
	dp = [0, 1, 2, 3, 2]

	for i in range(5, num + 1):
		pivot = 1
		tmp = 1_000_000
		while pivot ** 2 <= i:
			if 1 + dp[i - pivot ** 2] < tmp:
				tmp = 1 + dp[i - pivot ** 2]
			pivot += 1
		dp.append(tmp)

	return dp[num]


print(solution(int(input())))