[백준 1463 파이썬] 1로 만들기 (실버3, 다이나믹 프로그래밍)

알고리즘 유형 : 다이나믹 프로그래밍
풀이 없이 스스로 풀었나요? : ❌

---

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

솔루션

이 문제는 전의 결과를 다음 결과에 이용하게 되는 점화식을 활용한 DP 문제이다.

앞에서 구한 결과값을 저장하였다가 후에 사용하는 것이다.

일단, 2와 3으로 나누어 떨어지지 않는 경우는 무조건 1을 빼야 하기 때문에

dy[i] = dy[i-1] + 1을 통해 횟수를 +1 추가 해준다.

그리고나서, dy[i]가 2 와 3으로 나누어 떨어지는 경우에는

1을 빼는 것 보다 나누어 떨어지는게 훨씬 이득이기 때문에

min(dy[i], dy[i//2]+1)을 통해 최소값을 선택하면 된다.

소스 코드

import sys

input = sys.stdin.readline

if __name__ == "__main__":
    n = int(input())
    dy = [0] * (n + 1)
    for i in range(2, n + 1):
        dy[i] = dy[i-1] + 1
        if i % 2 == 0: 
            dy[i] = min(dy[i], dy[i // 2] + 1)
        if i % 3 == 0:
            dy[i] = min(dy[i], dy[i // 3] + 1)
    print(dy[n])

---

후기

조건식 작성 중 if elif else를 사용해서 시간이 오래걸렸다.
if만 이용해야 세 연산을 모두 거칠 수 있다.