백준 1463 - 1로 만들기

요구사항 숫자 n이 주어질때 1로 만드는 최소의 연산을 구하여라. 제약 조건 입력은 1 ~ 10^6의 정수가 된다.가능한 연산은 /3, /2, -1 이다. 1234567891011n = int(input())dp = [0, 0, 1, 1] + (pow(10,6) - 3) * [0] for i in range(4, n + 1): dp[i] = dp[i-1] + 1 if i % 3 == 0: dp[i] = min(dp[i],dp[i//3] + 1) if i % 2 == 0: dp[i] = min(dp[i],dp[i//2] + 1) print(dp[n])cs\ 문제 해결의 접근 dp 문제이기에 우선 점화식을 찾기 위해 접근하였다.1: [1], cnt = 02: [2,1], cnt = 13: [3,1], cnt = 14: [4,2,1], cnt = 25: [5,4,2,1], cnt = 36: [6,2,1], cnt = 27: [7,6,2,1] cnt = 38: [8,4,2,1] cnt = 39: [9,3,1] cnt = 210: [10,..........

원문링크 : 백준 1463 - 1로 만들기