백준 [1463]: 1로 만들기

📌 백준 [1463]: 1로 만들기

🔗 문제 링크

---

문제 설명 📄

양의 정수 X가 주어질 때, 정수 X에 사용할 수 있는 연산은 다음과 같다:

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

정수 X를 1로 만들기 위해 필요한 최소 연산 횟수를 구하라.

---

문제 접근 방식 💡

• BFS(너비 우선 탐색)를 사용하여 최단 경로를 탐색.
• 큐를 활용해 상태를 저장하고, 방문 여부를 체크하여 중복 계산 방지.

---

Solution 💻

from collections import deque
input = int(input())

q = deque()
pattern  = {}
q.append((input,0))

while q:
    p,count = q.popleft()
    if p in pattern:
        continue
    pattern[p] = 0
    if p == 1:
        print(count)
        break
    if p % 3 == 0:
        q.append((p//3 ,count+1))
    if p %2 == 0:
        q.append((p//2 , count + 1))
    q.append((p -1, count + 1))

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n)
  • 매 연산에서 최대 n개의 노드를 큐에 추가하고 방문 여부를 확인하기 때문.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(n)
  • 큐와 방문 집합이 최대 n개의 값을 저장할 수 있음.

---

리팩토링 🛠️

from collections import deque

input_value = int(input())

def min_operations_to_one(n: int) -> int:
    q = deque([(n, 0)])
    visited = set()

    while q:
        current, count = q.popleft()
        if current in visited:
            continue
        visited.add(current)

        if current == 1:
            return count

        if current % 3 == 0:
            q.append((current // 3, count + 1))
        if current % 2 == 0:
            q.append((current // 2, count + 1))
        q.append((current - 1, count + 1))

print(min_operations_to_one(input_value))

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n)
  • 매 연산에서 최대 n개의 노드를 큐에 추가하고 방문 여부를 확인하기 때문.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(n)
  • 큐와 방문 집합이 최대 n개의 값을 저장할 수 있음.