1로 만들기(백준)

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

1463번: 1로 만들기

 

내 풀이(문제를 잘 읽자)

n = int(input())

d = [0] * (10**6 + 1)

for i in range(2, n+1):
    d[i] = d[i-1] + 1

    if i % 3 == 0:
        d[i] = min(d[i], d[i//3] + 1)
    if i % 2 == 0:
        d[i] = min(d[i], d[i//2] + 1)
print(d[n])

이 문제도 어제 "이것이 취업을 위한 코딩테스트다"에서 푼 문제와 굉장히 유사하다. 사실 처음엔 풀지 못해서 어제 공부한 것을 다시 봤다. 그리고 나중에 풀었는데 런타임 에러가 떴었다. 알고보니 이 문제의 입력 범위는 10**6인데 나는 d 배열의 범위를 3001로 설정해줘서 틀렸었다. 이 문제는 보텀업 문제이다. 따라서 숫자가 낮은 거부터 최소한의 연산으로 만들 수 있도록 하면서 코딩을 하면 된다.