백준 BOJ 1463번 1로 만들기 실버3 - Python 풀이

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

1463번: 1로 만들기

문제

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

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

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

출력

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

소스 코드

import sys

n= int(sys.stdin.readline())
cnt=[99999 for i in range(n*3)]

cnt[1]=0

for i in range(1,n):
    cnt[i+1]=min(cnt[i]+1,cnt[i+1])
    cnt[i*2]=min(cnt[i]+1,cnt[i*2])
    cnt[i*3]=min(cnt[i]+1,cnt[i*3])

print(cnt[n])

전형적인 메모이제이션을 통해 푸는 다이나믹 프로그래밍 문제이다.

N을 1로 만드는 과정은 전혀 관심없고 몇 번의 연산인지 횟수만 구하면 되기 때문에,

2에서 1을 빼든 2를 2로 나누든 동일하다. 따라서 배열에 연산 횟수만 기록하며 갱신하면 된다.

 

정수 N에서 1을 만드는 연산은 1에서 N을 만든는 연산과 횟수가 동일하므로

1. X에 3을 곱한다.
2. X에 2를 곱한다.
3. 1을 더한다.

로 뒤집어서 연산할 수 있다.

cnt는 index가 n일 때 1에서 n을 만드는데 필요한 연산 횟수의 최솟값을 value로 가지는 배열이다.

1 부터 n 까지 반목문을 순회하며 cnt 배열에 각 index별 최솟값 value를 갱신한다.