[알고리즘][백준] 1463번 1로 만들기 - 파이썬(python) 풀이

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

1463번: 1로 만들기

---

단순하게 3의 배수로 만들고 진행하면 되겠다 싶어서 아래와 같이 코드를 작성했는데

import sys

n = int(sys.stdin.readline())

cnt = 0

'''

10 → 9 → 3 → 1

10 → 5 → 4 → 2 → 1

10 11 12 15

'''

while n != 1:

    if n % 3 == 1:

        n -= 1

        n //= 3

        cnt += 2

    elif n % 3 == 2:

        n -= 2

        n //= 3

        cnt += 3

    elif n % 3 == 0:

        n //= 3

        cnt += 1

    elif n % 2 == 1:

        n -= 1

        n //= 2

        cnt += 2

    elif n % 2 == 0:

        n //= 2

        cnt += 1

print(cnt)

오늘도 틀림~

 

다른분들 코드를 참고하니 

 

DP(다이나믹 프로그래밍)을 사용하시더라

import sys

n = int(sys.stdin.readline())

d = [0] * (n+1)

for i in range(2, n+1):     # 2 ~ n 까지 진행
    d[i] = d[i-1] + 1       # 3번 연산
    if i % 2 == 0:          # 2번 연산
        d[i] = min(d[i], d[i//2] + 1)
    if i % 3 == 0:          # 1번 연산
        d[i] = min(d[i], d[i//3] + 1)

print(d[n])