BOJ_1463 [ 1로 만들기 ] [ 파이썬 ]

문제

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

1463번: 1로 만들기

문제 해결 방법

top -bottom 방식으로

현재 숫자에서 3가지 연산을 했을 때 인덱스 값이 0 이라면 현재숫자까지 이동한 횟수 +1 을 해서 값을 갱신해준다.

dp[연산 후 값] = dp[연산 전 값] +1

 

소스 코드 보기

https://github.com/jokerKwu/BOJ_Algorithm/blob/master/python/BOJ_1463.py

jokerKwu/BOJ_Algorithm

import sys
n = int(sys.stdin.readline())
dp = [0 for _ in range(n+1)]
arr = [n]
while arr or dp[0] != 0:
    c_n = arr.pop()
    if c_n == 1:
        break
    if c_n % 2 == 0 and dp[c_n//2] == 0:
        dp[c_n//2] = dp[c_n] + 1
        arr = [c_n // 2] + arr
    if c_n % 3 == 0 and dp[c_n//3] == 0:
        dp[c_n//3] = dp[c_n] + 1
        arr = [c_n // 3] + arr
    if dp[c_n - 1] == 0:
        dp[c_n - 1] = dp[c_n] + 1
        arr = [c_n-1] + arr
print(dp[1])