백준 1463번: 1로 만들기 (파이썬)

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

1463번: 1로 만들기

 

문제

 

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

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

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

 

입력

 

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

 

출력

 

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

 

풀이

 

문제를 읽고 DP로 해결해야 하는 문제라고 생각했다.

arr 리스트는 인덱스 값을 1로 만들 때 필요한 최소 연산 횟수를 저장하는 리스트로 사용하였다. 예를 들어 arr[10]는 10을 1로 만들 때 필요한 최소 연산 횟수를 저장한다는 뜻이다. arr[1]은 아무 연산이 필요 없으니 0으로 초기화하고, 2 이상의 수부터 생각을 했다. 문제 조건에서 정수에 사용할 수 있는 연산은 3으로 나누어 떨어질 때 3으로 나누는 것, 2로 나누어 떨어질 때 2로 나누는 것, 1을 빼는 것이 있다고 한다. 각 숫자마다 어떤 연산을 사용할 수 있는지 확인하고, 가장 작은 값을 가지는 연산 횟수를 인덱스에 저장하는 방식으로 문제를 해결하였다.

 

소스 코드

n = int(input())

arr = [-1, 0]

for i in range(2, n+1):
    ans = arr[i-1] + 1
    if i%3 == 0:
        rule1 = arr[i//3] + 1
        ans = rule1 if rule1 < ans else ans
    if i%2 == 0:
        rule2 = arr[i//2] + 1
        ans = rule2 if rule2 < ans else ans
    arr.append(ans)
print(arr[n])