작심큰일 챌린지 - Day 10. 김밥천국의 계단 (미들러, Python)

출처 - 작심큰일 챌린지 메인 페이지

 

대망의 마지막 날이다. 

 

챌린지가 벌써 끝나다니, 역시 뭔가 꾸준히 루틴을 지키면 시간이 참 빨리 지나가는 것 같다.

 

---

Day 10. 김밥천국의 계단 

 

오늘의 문제는 백준 프로그래밍 28069번 문제다.

 

문제

민희는 미니김밥이 유명한 천국에 가려고 합니다.

 

천국 문 앞에는 무한히 많은 계단이 있고 가장 아래 계단의 번호가 0번이며, 위로 올라가면서 순서대로 번호가 붙어있습니다. 그중 $N$번째 계단 옆에 김밥 가게가 있습니다.

 

민희는 매번 다음의 2가지 행동 중 하나를 선택해서 총 $K$번 행동할 수 있으며, 정확히 $K$번째 행동에서 $N$번째 계단에 도달하면 미니김밥을 먹을 수 있습니다.

 

1. 계단 한 칸을 올라갑니다.
2. 민희가 집에서 가지고 온 지팡이를 계단에 두드립니다. 만약 민희가 $i$ 번째 계단에서 지팡이를 두드리면 $i +\left \lfloor \cfrac{i}{2} \right \rfloor$번째 계단으로 순간이동합니다.

 

현재 민희는 0번째 계단에 있습니다. 민희가 미니김밥을 먹을 수 있을지 구해 봅시다.

 

입력

첫 번째 줄에 계단 개수에 해당하는 $N$, 계단을 오르는 횟수 $K$가 주어진다. $(1 \leq N, K \leq 1\,000\,000)$ 

출력

민희가 $N$개의 계단을 $K$번 만에 올라 미니김밥을 먹을 수 있으면 minigimbob을, 그러지 못해 물만 마신다면 water을 출력한다.

 

예제 입력 1

5 2

예제 출력 1

water

 

예제 입력 2

42 10

예제 출력 2

minigimbob

 

---

풀이 과정

 

먼저 $i +\left \lfloor \cfrac{i}{2} \right \rfloor$가 정확히 무슨 뜻인지부터 확실히 알아보았다.

 

해당 문제의 힌트에서 알 수 있듯, 지팡이를 계단에 두드리면 현재 계단에서 2로 나눈 값을 내림으로한 정수값만큼 현재 계단에 그 수를 더하는 것이다.

 

표를 통해 보면 다음과 같다.

 

$i$	$i/2$	$i +\left \lfloor \cfrac{i}{2} \right \rfloor$	합계
5	2.5	2	7
4	2	2	6
3	1.5	1	4
2	1	1	3
1	0.5	0	1
0	0	0	0

 

BFS vs. DFS

보통 "최단 경로" 또는 "최단 거리"가 언급된 문제를 보면 BFS/DFS 같은 그래프 탐색 방법을 떠올리게 된다.

 

이번 김밥 문제에서는 처음엔 완전탐색이 바로 떠오르지는 않았지만, 문제의 핵심이 "민희가 주어진 K번 이내로 목적지에 도달할 수 있는지"에 있다는 점을 고려했을 때 어떤 식의 접근이 필요한지 좀 더 생각해 보았다.

 

해당 문제는 "최단 경로"를 구해 주어진 기회(K)로 도달이 가능한지만 판단하면 되므로, 이 문제 역시 BFS 또는 DFS 탐색 접근이 적합하다는 결론에 도달할 수 있다.

 

DFS는 경로의 깊이를 우선 탐색하여, 목적지에 도달했을 때의 ‘행동 수’가 반드시 최소라는 보장이 없다.

 

BFS는 목적지에 최초로 도달한 그 순간이 바로 '행동 수가 가장 적은' 경우임을 보장하기 때문에, 이 문제에서는 좀 더 올바른 접근이었다.

 

구현

 

앞선 고민들을 기반으로 알고리즘적 접근을 먼저 적어보았다.

 

1. 그래프 모델링
   • 각 계단을 노드로 보고, 가능한 이동(한 칸, 순간이동)을 간선으로 연결
   • 최단 경로(행동 수 최소화) 문제임을 인식
2. 최단 거리 탐색(BFS)
   • 활용시작점(0번 계단)에서 BFS로 탐색
   • 각 계단(노드)까지 도달하는 최소 행동 횟수를 기록
   • 두 가지 이동 방법에 따른 다음 계단으로 큐에 넣으며 탐색
3. 방문 및 행동 횟수 관리
   • 각 계단의 최소 행동 횟수만 기록
   • 이미 더 적은 행동으로 도달했던 계단은 다시 탐색할 필요 없음
4. 정답 판정
   • N번 계단에 도달한 행동 횟수가 K 이하인지 확인
   • 조건을 만족하면 "minigimbob" 출력, 아니면 "water" 출력

 

위 내용에서 한 가지 수정이 필요한 부분이 있었다.

 

계단 문제에서는 각 인덱스(계단 번호)가 노드이며,"한 칸 오르기"와 "순간이동" 두 케이스로 다음 위치를 직접 구할 수 있기 때문에 그래프 모델링은 불필요하다.

 

대신 아래와 같이 구성할 수 있다.

 

N, K = map(int, input().split())

visited = [False] * (N + 1)
min_turn = [float('inf')] * (N + 1)   # 최소값 비교를 위해 가장 큰 수로 구성

 

이후에는 BFS를 구현하는 방식에 대해 고민했고, min_turn 배열을 기반으로 한 비교 로직을 구성했다.

 

from collections import deque

def bfs(v):
    queue = deque()
    queue.append((v, 0))  # 시작 노드 v에서 출발, 행동횟수 0
    min_turn[v] = 0

    while queue:
        now, turns = queue.popleft()
        # 종료조건: 목표 도달 및 K 초과
        if now == N:
            return turns <= K
        # 한칸
        if now + 1 <= N and min_turn[now + 1] > turns + 1:
            min_turn[now + 1] = turns + 1
            queue.append((now + 1, turns + 1))
        # 순간이동
        teleport = now + (now // 2)
        if teleport <= N and min_turn[teleport] > turns + 1:
            min_turn[teleport] = turns + 1
            queue.append((teleport, turns + 1))
    return False

 

사실 v 라는 매개변수 없이도 함수 내부에 min_turn[v] = 0 대신 min_turn[0] = 0 으로 할당하여 함수를 구성할 수 있는데, 최대한 기본 틀을 지키고 함수의 재활용성을 높이기 위해 매개변수를 사용했다.

 

---

 

개선점

 

해당 문제는 DP(동적 계획법)를 활용하면 더 깔끔하게 코드를 구성할 수 있다.

 

 앞서 언급했듯, 나는 그래프 모델링을 생략하는 방식으로 코드를 구현했다.

 

N, K = map(int, input().split())

visited = [False] * (N + 1)
min_turn = [float('inf')] * (N + 1)   # 최소값 비교를 위해 가장 큰 수로 구성

 

하지만 아래와 같이 DP를 활용하면 점화식과 최소값 비교 연산으로 상태를 단순하게 관리가 가능하다.

 

n, k = map(int, input().split())

dp = [float("INF")] * (n + 1)
dp[0] = 0

 

먼저 점화식을 선언하고 기존과 같이 최소값 비교를 위해 가장 큰 수로 구성된 점화식을 구성한다.

 

다음은 해설에서의 코드다.

 

for i in range(1, n + 1):
    dp[i] = min(dp[i], dp[i - 1] + 1)
    if i + i // 2 <= n:
        dp[i + i // 2] = min(dp[i + i // 2], dp[i] + 1)

print("minigimbob" if dp[n] <= k else "water")

 

이 점화식은 `dp[i]`를 현재까지 도달하는 최소 행동 횟수로 정의하며, 한 칸 이동과 순간이동 두 경우를 모두 고려한다.

 

복잡한 분기문 없이 단순한 배열 업데이트만으로 최적해를 구할 수 있어 구현과 시간 면에서 유리하다. 코드 자체도 더 깔끔한데, 효율적이다. 역시 시니어