[백준] 1463. 1로 만들기 / python 파이썬

🚩 동적프로그래밍(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 계산먼저 해주고

    if i % 2 == 0 and dp[i] > dp[i//2] + 1:  # 2로 나눠지면서 카운팅횟수가 전보다 크면 바꾸기
        dp[i] = dp[i//2] + 1

    if i % 3 == 0 and dp[i] > dp[i//3] + 1:  # 3으로 나눠지면서 카운팅횟수가 전보다 크면 바꾸기
        dp[i] = dp[i//3] + 1

print(dp[N])  # == print(dp[-1])