[백준 1463번] 1로 만들기

핵심 아이디어

• i에서 1을 빼는 경우: dp[i-1] + 1
• i가 2로 나누어 떨어지면, 2로 나누는 경우: dp[i//2] + 1
• i가 3으로 나누어 떨어지면, 3으로 나누는 경우: dp[i//3] + 1

N =10일 경우 예시

i	dpi	1을 뺀 경우 (dp[i-1] + 1)	2로 나눈 경우 (dp[i//2] + 1)	3으로 나눈 경우 (dp[i//3] + 1)	최종 dp[i]
1	0	-	-	-	0
2	0	1 (dp[1] + 1)	1 (dp[1] + 1)	-	1
3	0	2 (dp[2] + 1)	-	1 (dp[1] + 1)	1
4	0	2 (dp[3] + 1)	2 (dp[2] + 1)	-	2
5	0	3 (dp[4] + 1)	-	-	3
6	0	4 (dp[5] + 1)	2 (dp[3] + 1)	2 (dp[2] + 1)	2
7	0	3 (dp[6] + 1)	-	-	3
8	0	4 (dp[7] + 1)	3 (dp[4] + 1)	-	3
9	0	4 (dp[8] + 1)	-	2 (dp[3] + 1)	2
10	0	3 (dp[9] + 1)	4 (dp[5] + 1)	-	3

코드

def dp_to_one(N):
    # DP 테이블 초기화 (0으로 채우고, index 1부터 사용)
    dp = [0] * (N + 1)

    # DP 테이블 채우기
    for i in range(2, N + 1):
        # 기본적으로는 1을 뺀 경우로 초기화
        dp[i] = dp[i - 1] + 1

        # 2로 나누어 떨어질 경우 최소값 갱신
        if i % 2 == 0:
            dp[i] = min(dp[i], dp[i // 2] + 1)

        # 3으로 나누어 떨어질 경우 최소값 갱신
        if i % 3 == 0:
            dp[i] = min(dp[i], dp[i // 3] + 1)

    # 결과 반환
    return dp[N]

# 입력 받기
N = int(input().strip())
print(dp_to_one(N))

결론

• 최적 부분 구조 특성: 작은 문제의 해답을 이용해 큰 문제를 해결할 수 있는 구조
• 문제 접근 방식: 이 문제에서는 N을 1로 만드는 과정을 N-1, N//2, N//3과 같은 하위 문제들을 해결함으로써 이루어짐
• 메모이제이션(Memoization): 한 번 계산한 결과를 저장하고 재사용하여 각 하위 문제를 한 번만 계산함.
• DP 테이블 크기: dp 배열의 크기는 N+1이며, 각 인덱스 i에 대해 dp[i-1], dp[i//2], dp[i//3] 값을 한 번씩만 계산함.
• 시간 복잡도: 모든 계산이 상수 시간 O(1)에 이루어지므로, 전체 알고리즘의 시간 복잡도는 O(N)으로 매우 효율적임.
• 공간 복잡도: 입력 크기 N에 비례하는 크기의 배열 dp를 사용하므로 공간 복잡도는 O(N)임.