[백준/dp] 1463번: 1로 만들기 (실버 3, python)

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

1463번: 1로 만들기

 

아이디어

dp 문제였다.

정수 x가 1이 되는 최솟값은 x - 1의 최솟값 + 1 과 x를 2나 3으로 나눈 몫의 최솟값 + 1(x가 2나 3으로 나누어떨어질 때)중 더 작은 수가 된다.

• x - 1의 최솟값 + 1
  만약 숫자 x가 있을 때 x에 -1을 해주는 경우이다. x - 1을 구하는 최솟값에 -1을 해주는 연산 횟수(1)을 더해서 만들어진다.
• x를 2나 3으로 나눈 몫의 최솟값 + 1(x가 2나 3으로 나누어떨어질 때)
  x가 2나 3으로 나누어떨어지는 경우, 나누어서 나오는 몫을 구하는 최솟값에 2나 3을 나누는 연산 횟수(1)을 더해서 만들어진다.

둘 다 x를 만드는 방법 중 하나이다. 그러므로 이 둘 중 더 작은 값이 최솟값이 된다.

전체 코드

x = int(input())
dp = [0] * (x + 1)
for i in range(2, x + 1):
    dp[i] = dp[i - 1] + 1
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i // 3] + 1)
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i // 2] + 1)

print(dp[x])