알고리즘
백준 2096번 내려가기 (JAVA)
박카스마시며코딩
2023. 7. 11. 16:37
https://www.acmicpc.net/problem/2096
2096번: 내려가기
첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.
www.acmicpc.net
저는 DP를 이용하여 문제를 해결하였습니다.
DP를 이용해 각 경우의 수의 최소값과 최대값을 확인하였습니다.
package BOJ.dp;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.function.Function;
public class BOJ_2096 {
private static final int NOT_VALID = -1;
private static final int INF = 987654321;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Function<String,Integer> stoi = Integer::parseInt;
StringTokenizer st = new StringTokenizer(br.readLine());
int n = stoi.apply(st.nextToken());
int[][] map = new int[n+1][3];
for(int i = 1 ; i <= n ; i++){
st = new StringTokenizer(br.readLine());
map[i][0] = stoi.apply(st.nextToken());
map[i][1] = stoi.apply(st.nextToken());
map[i][2] = stoi.apply(st.nextToken());
}
int[][] dp = new int[n+1][3];
for(int i = 0 ; i <= n ; i++){
Arrays.fill(dp[i],NOT_VALID);
}
int max = calMax(0,1,map,dp,n);
for(int i = 0 ; i <= n ; i++){
Arrays.fill(dp[i],NOT_VALID);
}
int min = calMin(0,1,map,dp,n);
System.out.println(max+" "+min);
}
private static int calMin(int depth, int position, int[][] map, int[][] dp, int n) {
if(depth > n){
return 0;
}
if(dp[depth][position] != NOT_VALID){
return dp[depth][position];
}
int result = INF;
for(int i = -1 ; i <= 1; i++){
int next = position + i;
if(next < 0 || next >= 3){
continue;
}
result = Math.min(result,calMin(depth+1,next,map,dp,n));
}
result += map[depth][position];
dp[depth][position] = result;
return result;
}
private static int calMax(int depth, int position, int[][] map,int[][] dp ,int n) {
if(depth > n){
return 0;
}
if(dp[depth][position] != NOT_VALID){
return dp[depth][position];
}
int result = 0;
for(int i = -1 ; i <= 1; i++){
int next = position + i;
if(next < 0 || next >= 3){
continue;
}
result = Math.max(result,calMax(depth+1,next,map,dp,n));
}
result += map[depth][position];
dp[depth][position] = result;
return result;
}
}