[파이썬, Python] 백준 1463: 1로 만들기

문제

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

1463번: 1로 만들기

코드

n = int(input())
d = [0] * (n+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])

설명

우선 n+1 개 만큼의 0으로 이루어진 리스트를 만들어준다.

이후 i번째의 값을 i-1번째에 1을 더해준 값으로 우선 지정해준다.

만약 i가 2혹은 3으로 나누어지는 수라면 이 수와 2혹은 3으로 나누고 1을 더한 수를 비교해서 작은 수를 값으로 지정한다.

이후 값을 출력한다.