[BOJ] 28069: 김밥천국의 계단 (JAVA)

문제

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

 

여담

0번째 계단에서 순간이동을 하면 제자리 위치라는 것을 알아차리지 못했다. 전에도 이 문제를 풀었는데 모르겠어서 그냥 풀이를 참고해서 풀고 넘어갔더니 제대로 익히지 못한 것 같다. 이번에는 꼭 다시 풀어봐야지! 

 

풀이

문제에 따르면 계단을 올라갈 수 있는 방법은 총 2가지이다. 

1. 한 칸 올라가기
2. i + i / 2 계단으로 순간이동하기

 

정확히 K번째 행동에서 N번째 계단에 도달해야 미니 김밥을 먹을 수 있다고 한다. 이때, 0번 계단에서 2번 연산을 수행하면 제자리에 위치하게 된다. (0 + 0 / 2 = 0) 

 

즉, N = 2, K = 4일 때  2번만에 N번째 계단에 도착할 수 있다면 다음과 같은 연산을 수행하면 되는 것이다. 

• 0번 계단 → 0번 계단 → 1번 계단 → 2번 계단

따라서 K번 내로만 N번째 계단에 도착할 수 있으면 된다. 

 

BFS

단순하게 BFS 탐색으로 풀이하면 된다. 자세한 내용은 아래의 코드를 참고하면 된다.

 

DP

현재 4번 계단에 위치했다고 생각해보자. 4번 계단에서 갈 수 있는 방법은 5번 계단(4 + 1)이나 6번 계단(4 + 4 / 2) 이다. 각 계단의 입장은 다음과 같다.

• 5번 계단 입장
  • 원래 나의 최소 횟수인 dp[5]vs 4번 계단을 거쳐서 오는 최소 횟수인 dp[4] + 1
• 6번 계단 입장
  • 원래 나의 최소 횟수인 dp[6] vs 4번 계단을 거쳐서 오는 최소 횟수인 dp[4] + 1

 

이를 점화식으로 표현하면 다음과 같다.

• dp[i + 1] = min(dp[i] + 1, dp[i + 1])
• dp[i + i / 2] = min(dp[i] + 1, dp[i + i / 2])

 

코드

BFS

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

public class Main {
    static int N, K;
    static boolean[] visited;
    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());
        visited = new boolean[N + 1];
        System.out.println(bfs());
    }
    
    public static String bfs() {
        Queue<Stair> queue = new LinkedList<>();
        queue.offer(new Stair(0, 0));
        visited[0] = true;
        
        while (!queue.isEmpty()) {
            Stair now = queue.poll();
            if (now.num == N && now.cnt <= K) {
                return "minigimbob";
            }
            
            if (now.cnt > K) break;
            
            // 한 칸 올라가기
            int next = now.num + 1;
            if (next <= N && !visited[next]) {
                queue.offer(new Stair(next, now.cnt + 1));
                visited[next] = true;
            }
            
            // 순간 이동하기
            next = now.num + now.num / 2;
            if (next <= N && !visited[next]) {
                queue.offer(new Stair(next, now.cnt + 1));
                visited[next] = true;
            }
        }
        return "water";
    }
    
    static class Stair {
        int num; // 계단의 번호
        int cnt; // 해당 계단까지 올라가는 횟수
        
        public Stair(int num, int cnt) {
            this.num = num;
            this.cnt = cnt;
        }
    }
}

 

DP

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

public class Main {
    static final int INF = 1_000_001;
    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());

        dp = new int[N + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;
        for (int i = 0; i < N; i++) {
            int next = i + 1; // 한 칸 올라가기
            if (next <= N) {
                dp[next] = Math.min(dp[next], dp[i] + 1);
            }

            next = i + i / 2; // 순간이동하기
            if (next <= N) {
                dp[next] = Math.min(dp[next], dp[i] + 1);
            }
        }
        System.out.println(dp[N] <= K ? "minigimbob" : "water");
    }
}

---

참고

https://ps.mjstudio.net/boj-28069

https://kjh8673a.github.io/algorithm/2023-05-24-boj-28069/