99클럽 코테 스터디 19일차 TIL + 김밥천국의 계단

문제

 

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

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

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

1. 계단 한 칸을 올라갑니다.
2. 민희가 집에서 가지고 온 지팡이를 계단에 두드립니다. 만약 민희가 i 번째 계단에서 지팡이를 두드리면 i+⌊i/2⌋번째 계단으로 순간이동합니다.

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

입력

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

출력

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

 

---

풀이

from collections import deque
import sys
input = sys.stdin.readline

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

# 도달할 수 있는 최대 값은 N + N//2 (이를 넘지 않도록 설정)
MAX = N + N // 2 + 1

# dp 배열: dp[i]는 i번째 계단에 도달할 때 최소 K번 이하로 도달할 수 있는 횟수
dp = [float('inf')] * MAX
dp[0] = 0  # 처음에는 0번 계단에 0번으로 도달

# BFS
queue = deque([0])  # 시작점은 0
while queue:
    cur = queue.popleft()
    for next_step in [cur + 1, cur + cur // 2]:  # +1, +현재//2
        if next_step < MAX and dp[next_step] > dp[cur] + 1:
            dp[next_step] = dp[cur] + 1
            queue.append(next_step)

# dp[N]이 K 이하이면 minigimbob, 아니면 water
if dp[N] <= K:
    print("minigimbob")
else:
    print("water")

처음 디피로 풀이를 진행하려고했으나 실패했다

시간초과의 늪이랄까,,

디피로 시간초과안나게 푸는 방법도 궁금하다

 

 

문제 출처

https://www.acmicpc.net/problem/28069