백준 1463번 (실버 3) : 1로 만들기

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

1463번: 1로 만들기

import sys

n = int(sys.stdin.readline().rstrip())

lists = [0]*(n+1)
answer = 0


for i in range(1,n+1):
    if i*3 <n+1 and (lists[i*3] == 0 or lists[i*3] > lists[i]+1):
        lists[i*3] = lists[i] + 1

    if  i*2 <n+1 and (lists[i*2] == 0 or lists[i*2] > lists[i]+1):
        lists[i*2] = lists[i] + 1

    if  i+1 <n+1 and (lists[i+1] == 0 or lists[i+1] > lists[i]+1):
        lists[i+1] = lists[i] + 1

print(lists[n])

- 0부터 n까지의 인덱스를 가지고 있는 lists를 만든 후, 1부터 차례대로 *3, *2 +1 한 인덱스에 현재까지의 계산 횟수를 넣어준다.

- 마지막에 n번째 인덱스에 들어있는 최종 횟수를 프린트 하면 해결되는 간단한 문제이다.