[이것이코딩테스트다] 1로 만들기

📄 문제개요

• 정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지 이다.

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

• 정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만드려고 한다. 연산을 사용하는 횟수의 최소값을 출력하시오.

🤔 문제분석

• 다이나믹 프로그래밍 문제이다.
• 특정 숫자에서 5로 나누었을때, 3으로 나누었을때, 2로 나누었을때, 1을 뺏을때 중 최적의 경로가 정답이 된다.
• X의 숫자가 주어지고, 탑다운 방식으로 5로 나누었을때, 3으로 나누었을때, 2로 나누었을때, 1로 뺐을때 중 으로 분기시켜, X가 1이 되었을때, 가장 연산이 작은 것을 골라서 정답을 도출 할 수 있다.
• 바텀업 방식에서는 1로 시작하여, 1에 5를 곱하고, 1에 3을 곱하고, 1에 2를 곱하고, 1을 더하는 방식으로 1에서 X까지 도달 될 수 있는 최적의 경우의 수를 구한다.
  • 너비우선탐색으로 문제를 해결 할 수 있다.
  • 반복문을 활용하여 문제를 해결 할 수 있다.

📝 의사코드

반복문을 활용한 문제 풀이

• 1부터 X까지 순회하는 반복문을 생성한다.

1. 1은 0이고, 1에서 갈수있는 경우의수 곱하기5, 곱하기3, 곱하기2, 더하기 1의 최소값을 갱신한다.
   • 여기서 min을 사용하는 이유는 6을 예로 들을 수 있는데 3을 예로 들을 수 있는데, 3은 1*3에서 3으로 오는경우와 1+1+1을 해서 오는경우가 존재하기때문에 항상 최소값을 선택해주어야한다.
   1. dp[i5] = min(dp[i]+1, dp[i5])
   2. dp[i3] = min(dp[i]+1, dp[i3])
   3. dp[i2] = min(dp[i]+1, dp[i2])
   4. dp[i+1] = min(dp[i]+1, dp[i+1])

너비우선탐색을 이용한 문제 풀이

1. 큐에 X의 숫자와 방문 카운트를 넣는다. queue.append((X, 0))
2. 큐를 하나씩 꺼내어 5로 나눌수 있다면 5로 나누고, 3을 나눌수 있다면 3을 나누고, 2를 나눌수 있다면 2로 나누고 1을 뺄수 있다면 빼서 큐에 넣는다.
3. X가 1이 도달되면 그 경로는 항상 최적의 경로임으로 반복문을 탈출하고 종료한다.

💻 코드

반복문을 활용한 문제 풀이

import sys
input = sys.stdin.readline
INF = int(1e9)

X = int(input())

dp = [INF for _ in range(X+1)]
dp[1] = 0

for i in range(1, X+1):
    if X >= i*5: # 5를 곱한다.
        dp[i*5] = min(dp[i] + 1, dp[i*5])
    
    if X >= i*3:
        dp[i*3] = min(dp[i] + 1, dp[i*3])
        
    if X >= i*2:
        dp[i*2] = min(dp[i] + 1, dp[i*2])
        
    if X >= i+1:
        dp[i+1] = min(dp[i] + 1, dp[i+1])
        
print(dp[X])

너비우선탐색을 활용한 문제 풀이

import sys
from collections import deque

input = sys.stdin.readline
# BFS로 문제를 풀어보자
X = int(input())

visited = [False for _ in range(X+1)]

queue = deque()
queue.append((X, 0)) # X를 시작점으로하고 타깃이 1이다.
visited[X] = True

while queue:
    x, cost = queue.popleft()
    if x == 1:
        print(cost)
        break
    
    if x % 5 == 0 and not visited[x//5]: # X를 5로 나눌수 있다면 5로 나눈다.
        visited[x//5] = True
        queue.append((x//5, cost + 1))
        
    if x % 3 == 0 and not visited[x//3]: # X를 3으로 나눌수 있다면 3으로 나눈다.
        visited[x//3] = True
        queue.append((x//3, cost + 1))
        
    if x % 2 == 0 and not visited[x//2]: # X를 2으로 나눌수 있다면 2으로 나눈다.
        visited[x//2] = True
        queue.append((x//2, cost + 1))
        
    if x - 1 >= 1 and not visited[x-1]: # X를 2으로 나눌수 있다면 2으로 나눈다.
        visited[x-1] = True
        queue.append((x-1, cost + 1))

🎯 피드백 및 개선사항

• 너비우선탐색 vs 반복문을 활용한 문제풀이
• 숫자가 매우 커질경우, 너비우선탐색의 시간복잡도가 빠를 것이다.
• 5를 곱하면서 기하급수적으로 숫자에 빠르게 접근하기때문에 큰수일 수록 훨씬 빠를것이라고 생각된다.

❓다른사람은 어떻게 풀었을까?

• 바톰업 방식을 활용하여 문제 풀이를 확인하였습니다.