[백준] 2096번 내려가기 (자바 풀이)
- 알고리즘 문제 해결(PS)/[백준]
- 2022. 3. 23.
문제
https://www.acmicpc.net/problem/2096
풀이
이 문제는 간단한 DP 문제였다. maxDp와 minDP를 따로 나누어서 해결하면 간단하다.
우선, maxDp의 경우는 아래와 같은 점화식을 세우면 된다.
maxDp[i][j] = i번째 줄에서 j번째 숫자를 선택할 때 최댓값 ( 0 <= j < 3 )
maxDp[i][0] = Math.max(maxDp[i-1][0], maxDp[i-1][1]) + arr[i][0];
maxDp[i][1] = Math.max(Math.max(maxDp[i-1][0], maxDp[i-1][1]), maxDp[i-1][2]) + arr[i][1];
maxDp[i][2] = Math.max(maxDp[i-1][1], maxDp[i-1][2])+arr[i][2];
0번째 숫자를 고르는 것은 이전에 0번 혹은 1번에서 내려왔을테니 이들 중 최댓값을 고르고
1번째 숫자를 고르는 것은 이전에 0번,1번,2번 에서 내려왔을 테니 이들 중 최댓값을 고르고
2번째 숫자를 고르는 것은 이전에 1번 혹은 2번에서 내려왔을테니 이들 중 최댓값을 고르면 된다.
minDp의 경우는 위와 반대로 점화식을 세우면 된다.
minDp[i][j] = i번째 줄에서 j번째 숫자를 선택할 때 최솟값 ( 0 <= j < 3 )
minDp[i][0] = Math.min(minDp[i-1][0], minDp[i-1][1]) + arr[i][0];
minDp[i][1] = Math.min(Math.min(minDp[i-1][0], minDp[i-1][1]), minDp[i-1][2]) + arr[i][1];
minDp[i][2] = Math.min(minDp[i-1][1], minDp[i-1][2])+arr[i][2];
코드
import java.io.*;
import java.util.*;
public class Baekjoon_2096 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int arr[][] = new int[N][3];
int maxDp[][] = new int[N][3];
int minDp[][] = new int[N][3];
for(int i=0; i<N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
arr[i][2] = Integer.parseInt(st.nextToken());
}
maxDp[0][0] = minDp[0][0] = arr[0][0];
maxDp[0][1] = minDp[0][1] = arr[0][1];
maxDp[0][2] = minDp[0][2] = arr[0][2];
for(int i=1; i<N; i++) {
maxDp[i][0] = Math.max(maxDp[i-1][0], maxDp[i-1][1]) + arr[i][0];
maxDp[i][1] = Math.max(Math.max(maxDp[i-1][0], maxDp[i-1][1]), maxDp[i-1][2]) + arr[i][1];
maxDp[i][2] = Math.max(maxDp[i-1][1], maxDp[i-1][2])+arr[i][2];
minDp[i][0] = Math.min(minDp[i-1][0], minDp[i-1][1]) + arr[i][0];
minDp[i][1] = Math.min(Math.min(minDp[i-1][0], minDp[i-1][1]), minDp[i-1][2]) + arr[i][1];
minDp[i][2] = Math.min(minDp[i-1][1], minDp[i-1][2])+arr[i][2];
}
int max = Math.max(maxDp[N-1][0], Math.max(maxDp[N-1][1], maxDp[N-1][2]));
int min = Math.min(minDp[N-1][0], Math.min(minDp[N-1][1], minDp[N-1][2]));
System.out.println(max +" " + min);
}
}
반응형
'알고리즘 문제 해결(PS) > [백준]' 카테고리의 다른 글
[백준] 17825번 주사위 윷놀이 (자바 풀이) (0) | 2022.03.25 |
---|---|
[백준] 2531번 회전 초밥 (자바 풀이) (0) | 2022.03.24 |
[백준] 1965번 상자넣기 (자바 풀이) (0) | 2022.03.23 |
[백준] 1149번 RGB 거리 (자바 풀이) (0) | 2022.03.23 |
[백준] 1022번 소용돌이 예쁘게 출력하기 (자바 풀이) (0) | 2022.03.22 |