[Algo] 백준 28069 김밥천국의 계단 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/17396

메모리 : 62340KB

시간 : 208ms

언어 : Java 11

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static class Node {
		int turn, stair;

		Node(int turn, int stair) {
			this.turn = turn;
			this.stair = stair;
		}
	}

	static int N, K;
	static int[][] dp;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		String ans = "water";
		boolean[] check = new boolean[N + 1];
		Queue<Node> q = new LinkedList<>();
		q.add(new Node(1, 0));
		q.add(new Node(1, 1));
		while (!q.isEmpty()) {
			Node n = q.poll();
			if (n.turn > K) {
				break;
			}
			if (n.stair == N) {
				ans = "minigimbob";
				break;
			}
			if (n.stair <= N && !check[n.stair + 1]) {
				q.add(new Node(n.turn + 1, n.stair + 1));
				check[n.stair + 1] = true;
			}
			if (n.stair + (n.stair / 2) <= N && !check[n.stair + (n.stair / 2)]) {
				q.add(new Node(n.turn + 1, n.stair + (n.stair / 2)));
				check[n.stair + (n.stair / 2)] = true;
			}

		}
		System.out.println(ans);
	}
}

풀이

bfs로 풀 수 있었다. 근데 문제를 보면서 dp로 풀고싶었다.. 그런데 생각이 나지 않아서 일단 bfs로 제출
dp의 아이디어! 사실 K번만에 N으로 간다 = K번안에 N으로 가면 된다 이다. 0에서 지팡이를 이용하면 0으로 가기때문에 만약 K번보다 적은 이동으로 N에 도착할 수 있다면 0에서 지팡이를 두드리고 있다가 이동하면 된다. 이 아이디어를 이용해 N까지 갈 수 있는 최소이동을 dp로 구하고, 그렇게 N까지 이동한 횟수가 K보다 작다면 이동할 수 있는 것으로 보는 것이다.