김밥천국의 계단

🍙 백준 28282 - 미니김밥 천국

처음엔 BFS/DFS 문제인 줄 알았는데, 알고 보니 정확히 K번의 행동으로 N번 계단에 도달 가능한지를 묻는 DP 문제였다.
DFS는 시간 초과, BFS는 메모리 초과, 슬라이딩 윈도우도 모두 실패… 결국 DP로 갈아탐.

🚀 문제 핵심 정리

• 0번 계단에서 시작
• 총 K번 행동 가능
• 행동 종류:
  • 1칸 걷기 → i → i+1
  • 워프 → i → i + floor(i/2)
• 정확히 K번 행동해서 N번 계단에 도달하면 "minigimbob", 아니면 "water" 출력

🧠 접근 방식 - 1차원 DP

dp[i] = i번 계단에 도달하는 최소 행동 수
를 저장하면서 DP 배열을 점진적으로 갱신함

✅ 전이 조건 (점화식)

• dp[i] = min(dp[i], dp[i - 1] + 1) → 걷기
• dp[i + i // 2] = min(dp[i + i // 2], dp[i] + 1) → 워프 (단, 범위 체크 필수)

🚫 워프 유효성 조건

if i + i // 2 <= n:
👉 워프한 위치가 범위를 넘으면 의미 없음. 불필요한 탐색/갱신 막기 위해 꼭 필요함.

💻 코드 예시

n, k = map(int, input().split())
dp = [float("inf")] * (n + 1)
dp[0] = 0

for i in range(n + 1):
    if i + 1 <= n:
        dp[i + 1] = min(dp[i + 1], dp[i] + 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")

✅ 마무리 한 줄 요약

탐색처럼 보이지만, 실제로는 위치마다 최소 행동 수를 누적하는 전형적인 1차원 DP 문제였다.