1로 만들기 썸네일형 리스트형 [백준] 1463번 - 1로 만들기 (파이썬 코드) (feat. DP) 1. 문제 https://www.acmicpc.net/problem/1463 2. 코드 n = int(input()) dp = [0 for i in range(n+1)] for i in range(2, 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]) 3. 알고리즘 점화식 : dp[N] = min(dp[N-1], dp[N//2] , dp[N//3]) + 1 1) 1을 빼준 경우를 우선 저장해놓는다. 2) 3으로 나뉠 경우, 1을 빼준 경우와 비교해서 최솟값을 저장한다. 3) 2로 나뉠 경우, 1을 빼준 경우(만약 2)에서 3으로 .. 더보기 이전 1 다음
