[백준 1463] 1로 만들기

문제

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

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

2. X가 2로 나누어 떨어지면, 2로 나눈다.

3. 1을 뺀다.

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

 

입력

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

 

출력

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

---

접근

처음에 위에서 주어진 조건대로 구현을 하려고 했지만 실패했다. 최소 연산을 해야하는 최적화문제이기 때문에 그리디 or 동적프로그래밍으로 풀 수 있겠다는 생각을 하였다. 하지만 여기서 그리디로 구현하면 최적해가 나올 수 없었고 동적프로그래밍을 사용하였다.

여기서 할 수 있는 연산은 -1, ÷2, ÷3이다. 어떠한 수가 이 세 개의 연산을 활용하여 1이 되는 것에 규칙이 있다.

2는 -1 또는 나누기 2를 한다. 3은 -1 또는 나누기 3을 한다. 이후 4, 5, 6 모두 세 가지 중 하나의 연산을 해야되고 이 수들은 2일 때의 횟수와 3일 때의 횟수와 연관이 있다. 

따라서 현재 숫자에서 1이 되는 최소 연산을 구하기 위해서는 세 가지 경우를 비교해보면 된다.

1. 어떠한 수 N은 N-1수가 1이 되기위해 사용한 연산에서 +1을 한다. 이것은 N-1에서 -1을 하면 1이 되는 것이다.

2. 어떠한 수 N이 2로 나누어 떨어진다면 N/2의 수가 1이 되는 연산의 횟수에서 +1을 한다.

3. 어떠한 수 N이 3으로 나누어 떨어진다면 N/3의 수가 1이 되는 연산의 횟수에서 +1을 한다.

2번과 3번은 2또는 3으로 나누어 떨어진다면 2또는 3으로 나누었을 때의 수에서 2 또는 3으로 나누면 되기 때문이다.

 

구현

숫자 2부터 N까지 경우의 수를 통해 최솟값을 구해나간다.

N = int(input())
dp = [0 for _ in range(N+1)]
dp[1] = 0

for i in range(2, N+1):
    # 첫 번째 경우
    dp[i] = dp[i-1] + 1
    
    # 두 번째 경우
    if i%2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)
    
    # 세 번째 경우
    if i%3 == 0:
        dp[i] = min(dp[i], dp[i//3]+1)

print(dp[N])