jenlog

🚩 동적프로그래밍(DP) thinking 1. 규칙을 찾아보려 했으나 실패 -> 규칙 없음 ! 2. DP 접근 인풋숫자의 크기만큼 배열을 만들고, 계산횟수를 해당 인덱스에 입력 & 비교하면서 최소 연산값을 구하는 것이다. 앞에서 부터 계산을 해가면서 카운팅을 늘려나가는 것이 핵심이다 ! ◾ 점화식 : dp(N) = min ( dp(N//3)+1, dp(N//2)+1 , dp(N-1)+1 ) ◾ 시간복잡도 : {배열의 크기 x O(1)} => O(N) 코드 N = int(input()) dp = [0 for _ in range(N+1)] # 인덱스가 N이 되도록 N+1 크기의 배열을 만듦 for i in range(2, N+1): dp[i] = dp[i-1] + 1 # dp(N-1)+1 계산먼저 해주고 i..