글 읽기 - 제 소스의 효율이 왜이리 폭망인 것일까요?[python3]

herdson 4년 전 0

도출된 값과 횟수를 리스트에 넣어가면서 꺼내오는 식으로 풀었는데 실행시간이 1800ms에 육박하는 결과가 나왔네요... 좀더 최적화 하는 방법은 무엇일까요?

DP는 이제 막 시작해보는거라 고수님들의 조언이 필요합니다..!

x = int(input())
simulator = [[1,0], [2, 1], [3, 1], [4, 2]]

for i in range(x):
    if i <= 3:
        continue
    
    case = [[i + 1, simulator[-1][1] + 1]]
    if (i + 1) % 3 == 0:
        case.append([i + 1, simulator[(i + 1) // 3 - 1][1] + 1])
    if (i + 1) % 2 == 0:
        case.append([i + 1, simulator[(i + 1) // 2 - 1][1] + 1])
    
    case.sort(key = lambda a : a[1])
    simulator.append(case[0])
    
print(simulator[x - 1][1])

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

문제

문제

출처

ICPC

제 소스의 효율이 왜이리 폭망인 것일까요?[python3]

herdson 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말