[Python] 1463. 1로 만들기

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

1463번: 1로 만들기

 

접근법

• 3가지 연산을 적절히 사용해 정수 N을 1로 만드는 문제이다.
• N을 만들 수 있는 모든 경우의 수를 찾되 min값을 찾는다.
• bottom-up 방식의 dp를 활용해서 arr[1] = 0부터 채워나간다.

def dp(start, end, arr):
    for i in range(start, end + 1):
        arr[i] = arr[i-1] + 1
        if i % 2 == 0:
            arr[i] = min(arr[i], arr[i//2]+1)
        if i % 3 == 0:
            arr[i] = min(arr[i], arr[i//3]+1)
    print(arr[end])

def main():
    n = int(input())
    arr = [0] * (n + 1) # 모든 arr의 초기값을 0으로 설정
    dp(2, n, arr)

if __name__ == "__main__":
    main()

---

사용된 알고리즘

다이나믹 프로그래밍