[백준] 1463. 1로 만들기 - 파이썬 풀이

문제

• 백준 1로 만들기

풀이 과정

• 그리디 알고리즘과 구분하기.
  • 그리디 알고리즘은 각 단계에서 최적의 해를 보장해야하지만, 이 문제는 무엇으로 나눌지에 따라서 최적의 해가 달라지기 때문에 DP로 풀어야한다.
  • 또한 입력 갯수와 시간 제한이 빡빡하기 때문에 이를 보고 유추했을 때, DP를 떠올릴 수 있다.
• 각 단계별로 네가지의 연산이 가능하기때문에 이 중에서 최솟값을 구해주면 된다. 따라서 이 문제의 점화식은 다음과 같다.
  • min(ai-1, ai/2, ai/3 ai/5). 나머지를 구하는 연산은 각 조건에 해당할 때만 수행할 수 있어야 한다. (a의 i-1번째, a의 i를 2로 나눔, a의 i를 3으로 나눔, a의 i를 5로 나눔의 의미)
• 이를 코드로 구현하면 다음과 같이 구현할 수 있다.
• +1을 해주는 것은 횟수를 구하는 것이기 때문에 카운팅을 해주는 의미라고 생각하면 된다.

코드

import sys
sys.stdin = open("1463_1로만들기_input.txt", "rt")

n = int(sys.stdin.readline())
dp = [0] * 1000001

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])