[Python 3] BOJ - 1463 "1로 만들기"

 # 문제 링크 : https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 # 풀이 :

이 문제는 다이나믹 프로그래밍으로 풀 수 있다. 왜냐하면 현재 수가 i라고 한다면 3i에서 3으로 나눠서 오는 방법이 있고, 2i에서 2로 나눠서 오는 방법, 마지막으로 i + 1에서 1을 빼서 i로 오는 방법 총 세가지가 있기 때문이다. 따라서 경우가 작은 경우로 나눌 수 있고 그것이 연관되어있기 때문에 이 문제는 다이나믹 프로그래밍이라 할 수 있다. 따라서 점화식은 아래의 그림과 같다

<그림 1. 점화식>

 점화식의 첫번째 경우는 i가 2로만 나누어 떨어지는 경우는 i/2와 i-1에서 i로 올 수 있고 그 두가지 경우 중 작은 경우에서 연산을 한번해야 i로 올 수 있으므로 1을 더해줘야 한다. 두번째의 경우는 i가 3으로만 나누어 떨어지는 경우이기 때문에 i/3과 i-1중 작은 경우를 골라 1을 더해주면 된다. 세번째의 경우는 i가 2와 3으로 나누어 떨어지는 경우기 때문에 모든 경우 중 작은 경우를 골라 1을 더해주면 된다. 네번째의 경우는 i가 2와 3중 어떠한 수로도 나누어 떨어지지 않는 경우기 때문에 i-1에서만 올 수 있으므로 이때는 1만 더해주면 i로 올 수 있는 모든 경우를 구할 수 있다.

 

 # 코드

import sys

# 입력부
a = int(sys.stdin.readline())
MAX = 10 ** 6 + 1

# dp : i로 가기 위한 최소 경우의 수
dp = [-1] * MAX

# 1,2,3 초기화
dp[1] = 0
dp[2] = 1
dp[3] = 1

# 점화식
for i in range(4, a + 1):
    if i % 2 == 0 and i % 3 != 0:
        dp[i] = min(dp[i // 2], dp[i - 1]) + 1
    elif i % 2 != 0 and i % 3 == 0:
        dp[i] = min(dp[i // 3], dp[i - 1]) + 1
    elif i % 2 == 0 and i % 3 == 0:
        dp[i] = min(dp[i // 2], dp[i // 3], dp[i - 1]) + 1
    else:
        dp[i] = dp[i - 1] + 1

# 정답출력
print(dp[a])