[백준] 1463. 1로 만들기 - 파이썬

• 백준 링크: 1463번: 1로 만들기
• solved.ac 난이도: 실버 III
• 시간 제한: Python3 - 1.5초 / PyPy3 - 0.7초
• 메모리 제한: 128MB

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.
   정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, $10^6$보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

코드

언어: 파이썬

def solution(N):
    N_arr = [0 for _ in range(1000001)]
    tmp = 0

    for i in range(2, N+1):
        N_arr[i] = N_arr[i - 1] + 1
        if i % 3 == 0:
            tmp = N_arr[int(i / 3)] + 1
            N_arr[i] = min(N_arr[i], tmp)
        if i % 2 == 0:
            tmp = N_arr[int(i / 2)] + 1
            N_arr[i] = min(N_arr[i], tmp)
    print(N_arr[N])

solution(int(input()))