[백준] 20869: 김밥천국의 계단 - JAVA

24 May 2023 in Algorithm on 다이나믹 프로그래밍

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

풀이

bfs와 dp로 접근할 수 있는 문제.

---

bfs

메모리: 57612KB

시간: 204ms

언어: Java 11

코드

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());

        System.out.println(bfs(N, K) ? "minigimbob" : "water");
    }

    private static boolean bfs(int n, int k) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        int[] cnt = new int[n + 1];

        while (!queue.isEmpty()) {
            int now = queue.poll();

            if(now == n && cnt[now] <= k) {
                return true;
            }
            
            if (cnt[now] == k) {
                continue;
            }

            int walk = now + 1;
            if (walk <= n && cnt[walk] == 0) {
                cnt[walk] = cnt[now] + 1;
                queue.add(walk);
            }

            int jump = now + now / 2;
            if (jump <= n && cnt[jump] == 0) {
                cnt[jump] = cnt[now] + 1;
                queue.add(jump);
            }

        }

        return false;
    }

}

---

dp

메모리: 57612KB

시간: 204ms

언어: Java 11

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[] dp = new int[N + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 0; i < N + 1; i++) {
            if (i + 1 <= N) {
                dp[i + 1] = Math.min(dp[i + 1], dp[i] + 1);
            }

            if (i + i / 2 <= N) {
                dp[i + i / 2] = Math.min(dp[i + i / 2], dp[i] + 1);
            }
        }

        System.out.println(dp[N] <= K ? "minigimbob" : "water");
    }

}