[Algorithm] 백준_김밥천국의 계단_28069번 (JAVA)

📝문제

---

💡풀이

문제 유형

다이나믹 프로그래밍

 

걸린 시간

1시간 30분

 

시간 복잡도

O(N)

 

풀이 방법 도출

1. 처음엔 bfs로 접근했다가 메모리 초과 문제로 dp로 돌렸다.
2. 문제가 좀 애매했던 거 같다.
3. 계단 오르는 횟수를 정확히 K번 가려면 dp[N]==K여야 하는 줄 알았지만
4. 생각을해보니 dp[0]은 순간이동으로 몇번째 행동에도 계속 0에 있을 수 있다.
5. 이는 곧 최소 횟수만 구하면 그 이후의 횟수는 맘대로 늘리기가 가능하다는 것이다.
6. 그래서 dp[N] <= K이기만 하면 답이 성립되는 것이다.
7. 아래 두 식을 사용하여 점화식으로 답을 구했다.
8. dp[i+1] = Math.min(dp[i+1], dp[i]+1)
9. dp[i+i/2] = Math.min(dp[i+i/2], dp[i]+1)

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

class Main {
    static final int INF = Integer.MAX_VALUE;

    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, INF);

        dp[0] = 0;

        for (int i = 0; i < N; 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");

    }
}

---

🤔Review

꽤 새로운 시각으로의 접근이 필요했던 문제였다.