오늘은 DP문제를 풀어보았다.
https://www.acmicpc.net/problem/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");
}
}
}
결과
'Coding Test' 카테고리의 다른 글
백준 암호만들기(1759) (0) | 2024.04.06 |
---|---|
백준 색칠하기(13265) (0) | 2024.04.02 |
백준 준규와 사과(5913) (0) | 2024.03.31 |
백준 십자뒤집기(10472) (0) | 2024.03.30 |
백준 회장뽑기(2660) (0) | 2024.03.29 |