백준 김바천국의 계단(28069)

 

오늘은 DP문제를 풀어보았다.

 

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

28069번: 김밥천국의 계단

 

 

해당 문제를 N * K 번 수행을 하게되면 메모리 초과 혹은 시간 초과가 발생된다.

 

해당 문제를 풀기 위해서 DP를 이용했다.

 

키 포인트

• 현재 계단이 밝을 수 있는 계단인가?
• 현재 계단은 몇번째 행위로 밝을 수 있는 계단 인가?

 

위 두가지 사항을 누적해가며 김밥 가게 위치에 최소 행동 값을 DP하면 된다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        solution();
    }


    public static void solution() 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[2][N + 1];

        Arrays.fill(dp[1], 1000000); // 최대 행동수로 세팅
        dp[1][0] = 0; // 맨 처음 0번 행동
        dp[0][0] = 1; // 0번째 계단 세팅

        for (int i=0 ; i < N + 1; i++) {
            if (dp[0][i] == 1) { // 해당 계단을 밝을수 있으면
                int n = i+1;
                if (n < N+1) {
                    dp[1][n] = Math.min(dp[1][n], dp[1][i]+1); // 행동 수 최소값 DP
                    dp[0][n] = 1; // 다음 계단 이동 가능 세팅
                }

                n = i + i/2;
                if (n < N+1) {
                    dp[1][n] = Math.min(dp[1][n], dp[1][i]+1); // 행동 수 최소값 DP
                    dp[0][n] = 1; // 다음 계단 이동 가능 세팅
                }

            }

        }

        if (dp[1][N] <= K) { // 김밥 가게 위치 행동수로 이동 가능 체크
            System.out.println("minigimbob");
        } else {
            System.out.println("water");
        }

    }
}

 

 

결과