[동적계획법/DP] 백준 17626 Four Squares - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

17626번: Four Squares

 

 

 

2. 문제 풀이

 최소의 제곱수 합으로 N을 구하는 문제입니다.

 

2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

 시간제한이 0.5초로 굉장히 짧습니다. 동적 계획법을 이용해서 이미 계산한 제곱수를 불러와서 사용합니다.

 

제곱수의 합 갯수 = min(현재까지 발견한 최소 갯수, 해당 제곱수를 더했을 때의 개수)

 

 

 

3. 코드

n = int(input())
cache = [0, 1] #1은 1

for i in range(2, n+1):
    squareN = 5 #최대 4개
    j = 1

    # j^2이 i보다 커지면 종료
    while j**2 <= i:
        # j**2를 추가했을 때, 제곱수가 작아지면 대체
        squareN = min(squareN, cache[i - j**2])
        j += 1
    # i일 때의 제곱수 메모 (+1은 추가한 j**2)
    cache.append(squareN+1)
print(cache[n])

 1부터 n까지 최소의 제곱수를 차례차례 구해갑니다.

 j**2를 추가했을 때 필요한 제곱합의 개수를 구하기 위해, cache[ i - j**2]를 참조합니다.

 해당 제곱 수를 추가한다는 건, 제곱수를 뺐을 때의 cache값에 +1를 하는 것과 같습니다.

 

 예를 들어, 26의 제곱합의 최소 개수는 아래 식에서 결정됩니다.

 min(5, cache[ 26 - 5**2 ]) = min(5, cache[1[) = min(5, 1) = 1, 최종 2.