[BOJ] 17626 : Four Squares [DP](Python)

문제 링크

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

17626번: Four Squares

소스 코드

from math import sqrt

n = int(input())
dp = [0] * (n+1)
dp[1] = 1

for i in range(2, n+1):
    min_count = 4
    for j in range(int(sqrt(i)), 0, -1):
        min_count = min(min_count, dp[i-j**2]+1)
    dp[i] = min_count

print(dp[n])

 

해설

• 최대 네 개의 제곱수를 활용하여 자연수를 만들 수 있다.

 

DP 테이블 초기화 후 각 제곱수 빼보기

예를 들어 n=2 인 경우, 범위를 1부터 0까지로 설정하여 그 범위에 해당하는 자연수들을 제곱하여 2에서 뺀다.

여기서는 2 - 1^2 이 되어 1이고, 여기에 1을 더한 값과 min_count = 4를 비교하여 작은 것을 취한다.

​

조금 더 큰 숫자로 예를 들면 n=10 인 경우, 범위를 3부터 0까지로 설정하여 자연수 3,2,1을 제곱하여 10에서 뺀다.

그러면 10 - 3^2 = 1 이므로 dp[i] + 1 = 2가 되고 이를 min_count = 4 와 비교하여 min_count 를 2로 갱신한다.

10 - 2^2 = 6 이므로 dp[6] + 1 = 4가 되고 이를 직전에 갱신된 min_count = 2와 비교한다.

마지막으로 10 - 1^2 = 9 이므로 dp[9] + 1 = 3이 되고 이를 min_count = 2와 비교하면 min_count = 2로 유지된다.

이를 dp[i] 에 저장해주면 된다.

 

요약

어떤 숫자 n이 있을 때, 이를 n보다 작거나 같은 자연수의 제곱으로 뺀 값을 인덱스로 삼는다.

'이 인덱스로 dp에서 값을 꺼내 +1을 한 것'과 '최대로 나올 수 있는 경우의 수 4'를 비교하여 작은 것을 취한다.

(4를 초과하는 값이 절대 나올 수 없는 구조)