[BOJ] 1463번: 1로 만들기

✏️ 문제

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

 

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

 

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

🤖 입출력 예시

 

💡풀이

정말 유명한 DP 문제 중 하나로, 솔직히 말해서 문제를 본 적은 많은데 오늘을 포함하여 자력으로 푼 적은 없다. 참 부끄러운 일이야~

 

오늘을 DP 공부의 날로 정했기 때문에 아주 세세하게 코드를 정리해보려고 한다.

 

1) 접근 방법

1. DP 테이블 정의

• 1차원 배열 형태의 DP 테이블 dp[i]에는 i를 1로 만들기 위해 필요한 최소 연산 횟수 저장
• 예) dp[3] = 1 (i=3이고 3으로 나누는 연산 한 번이면 1이 됨)

2. 초기값 설정

• dp[1] = 0
• 처음에 문제 풀 때 dp[1], dp[2], dp[3] 값을 다 주고 시작했는데 dp[2], dp[3]은 dp[1]만 알면 for문으로 처리가 돼서 굳이 초기값을 줄 필요는 없었음

3. ⭐ 점화식 설정 ⭐

• ① dp[i-1]+1 ② dp[i//2]+1 ③ dp[i//3]+1 이 세 가지 경우 중 최소값이 dp[i]에 저장됨

 

2) 예시

점화식 설정 단계 저 한 줄을 이해하는 데에 너무나 오래 걸려 버린 나의 두뇌,, 챗지피티님께서 친절히 작성해준 예시는 아래와 같다.

① dp[i-1]+1

i가 2와 3 그 어느 것으로도 나누어 떨어지지 않는 수라고 가정해보자. 즉, `i=5`라고 했을 때 `dp[5]=dp[4]+1`이라고 할 수 있는데 조금 더 풀어 쓰면 `dp[5] = dp[4](4를 1로 만들기 위해 필요한 연산 횟수)+1(5에서 1을 뺀 후 4로 가는 연산 횟수)`이다.

② dp[i//2]+1

i가 2로 나누어지는 경우인 `i=8`을 생각해보자. 이러한 경우에는 `dp[8] = dp[4](4를 1로 만들기 위해 필요한 연산 횟수)+1(8에서 2를 나눠 4로 가는 연산 횟수)`이라는 식이 성립하게 된다.

 

dp[i//3]+1도 위의 두 방식과 동일하기 때문에 생략!

 

3) 코드

import sys

N = int(sys.stdin.readline().strip())

dp = [0]*(N+1)

for i in range(2, N+1):
    dp[i] = dp[i-1]+1
    
    # i가 2로 나눠 떨어지는 경우
    if i%2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)
    
    # i가 3으로 나눠 떨어지는 경우
    if i%3 == 0:
        dp[i] = min(dp[i], dp[i//3]+1)
    
print(dp[N])

 

점화식 설정 단계 말고 코드 구현 단계에서도 하나 발목 잡혔던 부분이 있는데 '왜 dp[i] = dp[i-1]+1가 먼저 나오지?'를 이해 못 했었다.

 

근데 어려운 부분은 아니었고 그냥 '① dp[i-1]+1 ② dp[i//2]+1 ③ dp[i//3]+1 이 세 가지 경우 중 최소값'을 구하기 위해 1을 빼는 과정의 값을 미리 저장해두는 거였다. 1을 빼는 과정은 2로 나눠지거나 3으로 나눠지는 걸 생각하지 않고 모든 값에 공통으로 적용될 수 있는 것이기 때문에 가장 먼저 처리해주는 것이었음

 

🤓 참고

생각도 못했는데 풀이 좀 찾아보다 보니까 이 문제는 결국 최솟값을 구하는 거라 BFS로 푼 분들도 꽤 많았다. 그리고 이 문제는 BFS로 코드 제출하니까 DP 방식보다 수행 속도가 훨씬 빨라서 채찍피티한테 이유를 물어봤는데 설명을 요약하자면

 

"DP는 모든 수에 대해 연산을 진행하지만 BFS는 주어진 1로 도달하기까지 필요한 수에 대해서만 연산을 진행"

 

하기 때문에 BFS가 더 빠름 이었다. BFS 구현 코드는 아래에 함께 넣어둔다.

 

import sys

from collections import deque

def bfs_min_operations(n):
    queue = deque([(n, 0)])  # (현재 숫자, 연산 횟수)
    visited = set()  # 방문한 숫자들을 저장
    visited.add(n)
    
    while queue:
        current, operations = queue.popleft()
        
        # 현재 숫자가 1이라면, 연산 횟수를 반환
        if current == 1:
            return operations
        
        # 1을 빼는 경우
        if current - 1 > 0 and current - 1 not in visited:
            queue.append((current - 1, operations + 1))
            visited.add(current - 1)
        
        # 2로 나누는 경우
        if current % 2 == 0 and current // 2 not in visited:
            queue.append((current // 2, operations + 1))
            visited.add(current // 2)
        
        # 3으로 나누는 경우
        if current % 3 == 0 and current // 3 not in visited:
            queue.append((current // 3, operations + 1))
            visited.add(current // 3)

N = int(sys.stdin.readline().strip())

print(bfs_min_operations(N))

 

아 DP 잘하고 싶어라 ~