1463-1로 만들기

문제

설명만 보면 참 쉬운 문제같은데 위에 시간제한이 있어서 하나씩 다해보면 시간초과가 난다.

 

그래서 처음 1,2,3에서의 값은 0,1,1로 미리 추가해준 뒤 4부터 n까지 어차피 -1을 빼든 3이나 2로 나누든 그 값은 이전 숫자들이 포함되어 있기 때문에 더 빠르게 계산을 할 수 있게 만들어준다.

n = int(input())
count = 0
result = []
findmin = []
result.append(0)
result.append(1)
result.append(1)


for i in range(4,n+1):

    count = 1 + result[i-2]
    findmin.append(count)
    
    if(i%3 == 0):
        count = 1 + result[i//3-1]
        findmin.append(count)

    if(i%2 == 0):
        count = 1 + result[i//2-1]
        findmin.append(count)
    result.append(min(findmin))
    findmin.clear()

print(result[n-1])

이거푸는데도 오래걸림