[BOJ] 1463 - 1로 만들기

개요

2024.01.31 - [Alogrithm] 동적 계획법 (Dynamic Programming) 이란에서 동적 계획법의 개념과 접근 방식에 대해 간단히 살펴보았는데, 아무래도 관련 문제를 직접 해결해보는 편이 더 익숙해질 것 같아 문제를 풀어보려고 한다.

다만 이번 글에서는 다른 사람의 풀이(https://beginnerdeveloper-lit.tistory.com/81)를 참고한다.

 

🤔
비슷한 문제로 https://school.programmers.co.kr/learn/courses/30/lessons/154538 가 있는데, 이 문제는 직접 풀어보려고 한다.

 

 

문제

문제 : https://www.acmicpc.net/problem/1463

 

정수 X에 사용할 수 있는 연산은 세 가지이다.

• X가 3으로 나누어 떨어지면 3으로 나눈다.
• X가 2로 나누어 떨어지면 2로 나눈다.
• X에서 1을 뺀다.

임의 정수가 주어졌을 때 주어진 연산을 적절히 사용해 1을 만드려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하라.

 

 

접근

DP 문제이니 점화식을 구하는 것을 목표로 해보자. 연산을 f라고 하고, 정수 1부터의 결과를 차례대로 구해보면 다음과 같다.

\( n \)	\( f(n) \)
1	\( 1 = 1 \) \( \therefore \) 사용 연산이 없으므로 0
2	\( 2 \mod 2 = 0 \Rightarrow 2 / 2 = 1 \) \( \therefore 1 \)
3	\( 3 \mod 3 = 0 \Rightarrow 3 / 3 = 1 \) \( \therefore 1 \)
4	\( 4 \mod 2 = 0 \Rightarrow 4 / 2 = 2 \) \( \therefore f(2) + 1 \)
5	\( 5 \mod 3 \ne 0 \land 5 \mod 2 \ne 0 \Rightarrow 5 - 1 = 4 \) \( \therefore f(4) + 1 \)
6	\( 6 \mod 3 = 0 \Rightarrow 6 / 3 = 2 \) \( 6 \mod 2 = 0 \Rightarrow 6 / 2 = 3 \) \( \therefore min(f(2) + 1, f(3)+ 1) \)
7	\( 7 \mod 3 \ne 0 \land 7 \mod 2 \ne 0 \Rightarrow 7 - 1 = 6 \) \( \therefore f(6) + 1 \)
8	\( 8 \mod 2 = 0 \Rightarrow 8 / 2 = 4 \) \( \therefore f(4) + 1 \)

 

각 n에 대한 결과를 살펴보면, 아래와 같은 점화식을 구할 수 있다. 

$$ f(n) = 
\begin{cases} 
f(n / 3) + 1, & \mbox{if }n \mod 3 = 0 \\
f(n / 2) + 1, & \mbox{if }n \mod 2 = 0 \\
f(n - 1) + 1
\end{cases} 
$$

수식으로는 표현을 못 했는데 f(n)은 세 가지 경우 중 최솟값이 된다.

 

 

구현

2022.08.22 - [Algorithm] 메모이제이션(Memoization)에서 살펴본 피보나치 함수와 비슷하게 중복되는 연산이 많아 메모이제이션을 사용하면 좋을 것 같다.

정수 n을 입력받아 연산의 수를 반환하는 함수를 작성한다.

 

1. 메모이제이션을 위한 테이블 초기값을 설정한다.

memo = [0, 0]

 

2. 구한 점화식을 구현한다.

정수가 3으로 나누어질 때, 2로 나누어질 때를 모두 고려해 최소 연산 횟수를 구해야 한다. 

cnt = memo[i - 1] + 1
if i % 3 == 0:
    cnt = min(cnt, memo[i // 3] + 1)
if i % 2 == 0:
    cnt = min(cnt, memo[i // 2] + 1)
memo.append(cnt)

 

3. 테이블에서 n을 key로 하여 저장된 값을 반환한다.

return memo[n]

 

전체 코드는 접은글로 작성해둔다.

def solution(n):
    memo = [0, 0]
    for i in range(2, int(n) + 1):
        cnt = memo[i - 1] + 1
        if i % 3 == 0:
            cnt = min(cnt, memo[i // 3] + 1)
        if i % 2 == 0:
            cnt = min(cnt, memo[i // 2] + 1)
        memo.append(cnt)
    return memo[n]


n = int(input())
print(solution(n))

 

 

참고 문서

https://beginnerdeveloper-lit.tistory.com/81