[테스트케이스 추가] 백준 1699 시간초과 해결 python

1. 문제

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

1699번: 제곱수의 합

 

 

2. 풀이

동전2랑 유사한 문제. 

제곱의 수들을 미리 만들어 놓는 게 좋고, 시간복잡도 때문에 min 비교를 i 마다 해야 시간초과를 피할 수 있다.

 

 

 

3. 구현

import sys
import math

#sys.stdin=open('input.txt')

N=int(sys.stdin.readline())
mm=[math.inf]*int(N+2) #최소 math.inf
mm[0]=0
mm[1]=1
sqr=[i*i for i in range(1,int(N**0.5)+1)]

for i in range(1,N+2):
    tmp=[]
    for j in sqr:
        if i<j:
            break
        tmp.append(mm[i-j]+1)
    mm[i] = min(tmp)

if mm[N]==math.inf:
    print(-1)
else:
    print(mm[N])

 

4. 테스트케이스 추가

27

답: 3

 

52

답: 2

 

111

답: 4