백준(Baekjoon) 1463번 : 1로 만들기 with Python

 

백준에서 문제 보기 : https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

난이도

실버 3

알고리즘

1) 0으로 리스트 초기화

2) 점화식 이용 

   f(x - 1) + 1

   f(x / 2) + 1

   f(x / 3) + 1

 최소값 구하기

 

해결 방안

문제에서 요구하는 사항은 'DP(Dynamic programming)'를 구현하여 해결하는 개념을 요구합니다.

 

import sys

input = sys.stdin.readline

N = int(input())

dp = [0 for _ in range(N+1)]

for i in range(1, N+1):
    if i == 1:
        dp[i] = 0
        continue
    dp[i] = dp[i - 1] + 1
    if i % 3 == 0 and dp[i // 3] + 1 < dp[i]:
        dp[i] = dp[i // 3] + 1
    if i % 2 == 0 and dp[i // 2] + 1 < dp[i]:
        dp[i] = dp[i // 2] + 1

print(dp[N])

 

출력

리스트를 쓰지 않고 구현했다가는 시간초과 나기 쉽상이다