[백준알고리즘] 1699번: 제곱수의 합 -Python

[백준알고리즘] 1699번: 제곱수의 합 -Python

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

1699번: 제곱수의 합

이번 문제는 Python3로 통과하지 못하고 PyPy3로 통과할 수 있었다. Python3 통과자들의 시간도 매우 높은 것으로 보아 조금의 차이만 있는 것 같다.

 

PyPy3을 통과한 다른 분들의 코드도 참고해봤는데 같은 내용인데 조금씩 작성만 다르게 했다.

 

내가 푼 방식은 우선 최소 값을 구하는 것이기 때문에 범위의 최댓값으로 초기 리스트를 생성한다. 이후 제곱수들만 모아놓는 리스트를 만들어 놓는다.

 

그리고 N까지 가면서 제곱수들의 합으로 표현될 수 있는 모든 방법의 수를 비교해서 최솟값을 유지하도록 한다. 이때 비교는 배열에 각 수를 구하기 위한 제곱수들의 합의 최소 횟수가 저장되어 있는 것을 이용해서 구한다.

 

말로 하면 간단한데, 처음에는 무조건 N과 N보다 작고 가까운 가장 큰 제곱수의 차를 구해서 그 횟수를 더했다. 밑에 참조했던 예제인데 참조해보면 알 것 같다. 즉, 무작정 큰 수를 빼는 것은 답이 아니다.

 

142 = 121 + 16 + 4 + 1    -> 4

142 = 81 + 36 + 25          -> 3

12 = 9 + 1 + 1+ 1  -> 4

12 = 4 + 4 + 4       -> 3

 

import sys

N = int(sys.stdin.readline())
square = []
arr = [100000] * (N+1)

for i in range(N + 1):
    el = i**2
    if el > N:
        break
    square.append(el)
    arr[el] = 1

for idx in range(N + 1):
    for sq in square:
        if idx < sq:
            break
        arr[idx] = min(arr[idx], arr[sq] + arr[idx-sq])

sys.stdout.write(str(arr[N]))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다