99클럽 코테 스터디 19일차 TIL - 백준 28069번 : 김밥천국의 계단

✅ 문제

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

✅ 문제 유형

DP

BFS

✅ 공부한 내용

 

🔑 풀이

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); // 계단 수
        int K = Integer.parseInt(st.nextToken()); // 최대 허용 단계 수

        int[] visited = new int[N + 1]; // 방문 배열
        Queue<Integer> q = new LinkedList<>();

        visited[0] = 1; // 0번 계단에서 시작
        q.offer(0);

        while (!q.isEmpty()) {
            int u = q.poll();

            // 1. 한 칸 올라가기
            int v_up = u + 1;
            if (v_up <= N && visited[v_up] == 0) {
                visited[v_up] = visited[u] + 1;
                q.offer(v_up);
            }

            // 2. 지팡이 두드리기 (순간이동)
            int v_staff = u + (u / 2);
            if (v_staff <= N && visited[v_staff] == 0) {
                visited[v_staff] = visited[u] + 1;
                q.offer(v_staff);
            }
        }

        // 결과 출력
        if (visited[N] != 0 && visited[N] - 1 <= K) {
            System.out.println("minigimbob");
        } else {
            System.out.println("water");
        }
    }
}

참고

https://velog.io/@99mon/BOJ-28069-%EA%B9%80%EB%B0%A5%EC%B2%9C%EA%B5%AD%EC%9D%98-%EA%B3%84%EB%8B%A8