[백준 / 27440 / Python] 1 만들기

😮 문제가 뭔가요?

숫자 N이 주어지면 아래 세 가지 연산 중 하나를 선택해서 1을 만들어야 해요:

1. 3으로 나누어 떨어지면 ➡️ 3으로 나누기
2. 2로 나누어 떨어지면 ➡️ 2로 나누기
3. 1 빼기

목표는 가장 적은 횟수로 1을 만드는 거예요!

🔗 백준에서 직접 풀어보기

---

😅 처음 생각나는 방법 (근데 이건 틀렸어요!)

처음에는 이렇게 생각하기 쉬워요:
"3으로 나누는 게 제일 빨리 작아지니까, 3으로 나눌 수 있을 때는 무조건 3으로 나누자!"

N = int(input())
count = 0

while N != 1:
    if N % 3 == 0: 
        N //= 3
    elif N % 2 == 0:  
        N //= 2
    else:
        N -= 1 
    count += 1

print(count)

❌ 근데 이렇게 하면 안 되는 이유!

예를 들어 N = 10일 때:

• 위 코드대로 하면: 10 → 5 → 4 → 2 → 1 (4번 해야 함)
• 실제 최적의 방법: 10 → 9 → 3 → 1 (3번이면 됨!)

즉, "무조건 3으로 나누자!"라는 전략이 항상 최고의 방법은 아니에요.

---

🌟 BFS로 해결하기

BFS는 최단 거리를 찾는 알고리즘이에요. 미로에서 출구를 찾는 것처럼,
1을 만드는 가장 빠른 방법을 찾아줘요!

💡 BFS 코드

from collections import deque

N = int(input())
queue = deque([(N, 0)])  # (숫자, 지금까지 연산 횟수)
visited = set()  # 이미 계산한 숫자는 다시 계산하지 않아요

while queue:
    num, count = queue.popleft()

    if num == 1:  # 1을 만들면 성공!
        print(count)
        break

    # 3으로 나누기
    if num % 3 == 0 and num // 3 not in visited:
        queue.append((num // 3, count + 1))
        visited.add(num // 3)

    # 2로 나누기
    if num % 2 == 0 and num // 2 not in visited:
        queue.append((num // 2, count + 1))
        visited.add(num // 2)

    # 1 빼기
    if num - 1 not in visited:
        queue.append((num - 1, count + 1))
        visited.add(num - 1)

🎮 어떻게 동작하는지 보자!

N = 10일 때:

1. 처음: 10에서 시작
2. 가능한 선택:
   • 2로 나누기 → 5
   • 1 빼기 → 9
3. 9에서:
   • 3으로 나누기 → 3
4. 3에서:
   • 3으로 나누기 → 1 도착!

총 3번만에 도착! 👏

🤔 왜 BFS가 좋은가요?

1. 모든 가능한 방법을 단계별로 확인해요
2. 가장 먼저 1에 도달하는 방법이 최소 횟수를 보장해요
3. 실수할 걱정 없이 컴퓨터가 최적의 방법을 찾아줘요

🎯 연습해보기

다음 숫자들로 연습해보세요:

1. N = 12
2. N = 15
3. N = 27
4. N = 100

코드를 실행해보고 결과를 확인해보세요!
궁금한 점 있으면 언제든 물어보세요~ 😊