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

 

19일차 문제

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

 

 

 

문제 풀이

bfs로 풀이하였다.

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

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()); // 계단 오르는 횟수

		boolean[] visitied = new boolean[N+1];
		Queue<int[]> q = new LinkedList<>();

		q.add(new int[] {0, 0}); // 시작 위치, 이동 횟수
		visitied[0] = true;

		while(!q.isEmpty()) {
			int[] now = q.poll();

			// 이동 횟소 초과
			if(now[1] > K) {
				continue;
			}

			if(now[0] == N) {
				System.out.println("minigimbob");
				return;
			}

			// 1칸 이동
			int step = now[0] + 1;
			if(step <= N && !visitied[step]) {
				visitied[step] = true;
				q.add(new int[] {step, now[1] + 1});
			}

			// 지팡이로 점프 이동
			int jump = now[0] + now[0] / 2;
			if(jump <= N && !visitied[jump]) {
				visitied[jump] = true;
				q.add(new int[] {jump, now[1] + 1});
			}
		}

		System.out.println("water");
	}   
}