[동적계획법/DP] 백준 1699 제곱수의 합 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1699번: 제곱수의 합

 

 

 

2. 문제 풀이

 가장 적은 제곱수의 합으로 N을 구하는 문제입니다.

 

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

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

 전형적인 DP문제인 베낭문제와 비슷합니다. N보다 작은 제곱수를 1부터 순차적으로 넣어가며, 넣었을 때와 안 넣었을 때를 비교합니다. 넣는 게 이득이면, 해당 제곱수를 더하는 걸로 갱신합니다.

 

 

 

3. 코드

n = int(input())

square = [x**2 for x in range(1, 318)] # 제곱수
cache = [x for x in range(n+1)] # 캐싱
for i in range(n+1):
    for s in square:
        # 제곱수가 i보다 크면 break
        if s > i:
            break
        # 해당 제곱수로 더하는 게 더 작으면 갱신
        cache[i] = min(cache[i], cache[i-s]+1)
print(cache[n])

 입력은 최대 100000(10만)까지 주어집니다. 루트 10만은 316.xxx로 317의 제곱수까지 구해줍니다.