shuangjutou   2년 전

파이썬... 으로 풀다가 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로 바꾸면 통과합니다.

저는 똑같다고 생각했지만, 파이썬에서 제곱 연산을 할 때... 아무래도 ** 연산자보단 그냥 * 연산자를 쓰는게 훨씬 빠른가 봅니다.

시간 초과로 통과가 되냐/안되냐를 가를 정도로요...

ahmg1216   2년 전

아마 *는 단순히 곱하기지만 **는 특정 횟수만큼 곱하는 기능까지 포함되어 시간이 더 걸리는 듯 합니다

chhc0505   1년 전

저도 40분동안 머리 아프다가 이제 속 시원하네요 ㅠㅠㅠ

정말 감사합니다!

rhzn5512   1년 전

ㄹㅇ 개추입니다ㅋㅋㅋㅋㅋㅋ저도 똑같이 **2 하다가 아 왜 안돼 3번 반복하고 혹시? 하다가 바꿨는데 진짜 속이 뻥

댓글을 작성하려면 로그인해야 합니다.