[백준] 1463번 1로 만들기(python)

1. 문제

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

2. 풀이

dp를 사용해 문제를 풀었으며 최소로 만들기 위한 조건이 - 1을 하였을 경우가 다음 값이 가장 최소이기 때문에
dp[i] = dp[i - 1] + 1 이라는 것을 발견하였고, 이를 통해 2로 나눠진다면 2로 나눈 값과 최소 비교를 3으로 나눠지는 경우는 3으로 나눈값과 최소 비교를 하도록 하였다.

3. 코드

import sys

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

for i in range(2, n + 1):
    # 이전의 최소 값의 + 1을 한 값이 가장 최소값이 됨
    # 1을 뺀다.라는 조건을 되돌렷을때 가장 변화가 작기때문
    # 1을 더할 경우 2일 때 -> 3, 2를 곱할 경우 -> 4, 3을 곱할 경우 -> 6 이 되기 때문
    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])

초기 오답코드

import sys

n = int(sys.stdin.readline())
cnt = 0
while True:
    if n == 1:
        break

    if n % 3 == 0 or (n - 1) % 3 == 0:
        if n % 3 == 0:
            n //= 3
            cnt += 1
        else:
            n -= 1
            n //= 3
            cnt += 2
    else:
        n //= 2
        cnt += 1
print(cnt)```