파이썬... 으로 풀다가 40분동안 골싸매고 멘탈이 나간 후 정보를 공유하고자 글을 씁니다.
import sys
import math
n = int(sys.stdin.readline().rstrip())
memo = [_ for _ in range(100001)]
for i in range(1, n+1):
for level in range(1, math.floor(i ** (1/2))+1):
if memo[i - level**2] < memo[i]:
memo[i] = memo[i - level**2] + 1
print(memo[n])
저는 최종적으로는 위와 같은 코드로 풀었는데요.. 사실 위의 코드는 python으로 제출하면 시간 초과가 납니다. pypy로 제출하면 통과할거구요.
계속 시간 초과가 나길래 뭐가 문제일까 다른 분들의 코드 로직을 봐도 크게 다를 것이 없었고, 다른 분들의 코드와 동일하도록 수정해나가다가 문제가 무엇인지 파악했습니다.
다른 분들의 코드와 한 가지 다른 점이 있었습니다.
제곱을 할 때 level**2 로 했다는 점입니다.
위 코드는 level**2 부분을 level*level로 바꾸면 통과합니다.
저는 똑같다고 생각했지만, 파이썬에서 제곱 연산을 할 때... 아무래도 ** 연산자보단 그냥 * 연산자를 쓰는게 훨씬 빠른가 봅니다.
shuangjutou 2년 전 5
파이썬... 으로 풀다가 40분동안 골싸매고 멘탈이 나간 후 정보를 공유하고자 글을 씁니다.
저는 최종적으로는 위와 같은 코드로 풀었는데요.. 사실 위의 코드는 python으로 제출하면 시간 초과가 납니다. pypy로 제출하면 통과할거구요.
계속 시간 초과가 나길래 뭐가 문제일까 다른 분들의 코드 로직을 봐도 크게 다를 것이 없었고, 다른 분들의 코드와 동일하도록 수정해나가다가 문제가 무엇인지 파악했습니다.
다른 분들의 코드와 한 가지 다른 점이 있었습니다.
제곱을 할 때 level**2 로 했다는 점입니다.
위 코드는 level**2 부분을 level*level로 바꾸면 통과합니다.
저는 똑같다고 생각했지만, 파이썬에서 제곱 연산을 할 때... 아무래도 ** 연산자보단 그냥 * 연산자를 쓰는게 훨씬 빠른가 봅니다.
시간 초과로 통과가 되냐/안되냐를 가를 정도로요...