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
🌿 - 문제 설명
📌- 풀이
여러가지 방법들을 생각해봤다. 처음부터 아래까지 전부 완전 탐색을 하면 어떨까?
이런식으로 계속해서 완전탐색을 하게 된다면 결과값이 나오게 될 것이다.
하지만 여기서 문제점이
N이 최대 10만까지 이므로 숫자가 늘어날수록 연산해야 할 양이 기하급수적으로 늘어나기 때문에 분명 시간초과가 날 것으로 예상된다.
여기서 다른 방법으로 DP를 생각했다.
DP(다이나믹 프로그래밍)이란?
https://hongjw1938.tistory.com/47
알고리즘 - Dynamic Programming(동적 계획법)
1. 개요 DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로
hongjw1938.tistory.com
여기에 자세하게 나와있지만 짧게 요약하자면
하나의 큰 문제를 여러개의 작은 문제로 나누어서 결과를 저장하고 그 결과들로 다시 큰 문제를 만드는 것.
이 문제에서
arr[i][j] 값을 구하기 위해서 이전 값들의 최소값과 최댓값이 필요하기 때문에
min값과 max값들을 각각의 배열에 저장해주면서 현재 값을 업데이트 시켜주면 된다고 생각했다.
arr[i][j] 의 최소값과 최대값은
j가 0일 때는 arr[i][-1]의 값이 없기 때문에 j, j+1
maxDp[i][j] = Math.max(maxDp[i-1][j],maxDp[i-1][j+1]) + arr[i][j];
minDp[i][j] = Math.min(minDp[i-1][j],minDp[i-1][j+1]) + arr[i][j];
j가 1일 때는 전부 다 비교를 해줘야 하기 때문에
maxDp[i][j] = Math.max(Math.max(maxDp[i-1][j],maxDp[i-1][j+1]),maxDp[i-1][j-1]) + arr[i][j];
minDp[i][j] = Math.min(Math.min(minDp[i-1][j],minDp[i-1][j+1]),minDp[i-1][j-1]) + arr[i][j];
j가 2일 때는
maxDp[i][j] = Math.max(maxDp[i-1][j],maxDp[i-1][j-1]) + arr[i][j];
minDp[i][j] = Math.min(minDp[i-1][j],minDp[i-1][j-1]) + arr[i][j];
이런식으로 DP 배열을 쌓아갔고, 마지막까지 결과를 계산하고 나온 최대값과 최소값을 출력해주는 것으로 마무리 했다.
int n = Math.max(Math.max(maxDp[N - 1][0], maxDp[N - 1][1]), maxDp[N - 1][2]);
int m = Math.min(Math.min(minDp[N - 1][0], minDp[N - 1][1]), minDp[N - 1][2]);
System.out.println(n + " " +m);
DP 문제 치고 어려운 편은 아니었지만 빠르게 점화식을 세워서 한번만에 정확하게 푼 문제여서 한번 정리를 해보고 싶었다.
다른 DP문제들도 더 잘 풀 수 있도록 많이 풀어보자
🔥 - Java 전체 코드
package DP.G5_2096_내려가기;
import java.io.*;
import java.util.*;
public class Main {
public static int N,M;
static int[][] arr;
static int[][] maxDp, minDp;
public static void main(String[] args) throws IOException {
//BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedReader br = new BufferedReader(new FileReader("src/input.txt"));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(st.nextToken());
arr = new int[N][3];
maxDp = new int[N][3];
minDp = new int[N][3];
for(int[] list : minDp){
Arrays.fill(list,Integer.MAX_VALUE);
}
for(int i =0;i<N;i++){
st = new StringTokenizer(br.readLine());
for(int j=0;j<3;j++){
int num = Integer.parseInt(st.nextToken());
if (i == 0) {
minDp[i][j] = num;
maxDp[i][j] = num;
}
arr[i][j] = num;
}
}
for(int i =1;i<N;i++){
for(int j =0; j<3;j++){
if(j ==0){
maxDp[i][j] = Math.max(maxDp[i-1][j],maxDp[i-1][j+1]) + arr[i][j];
minDp[i][j] = Math.min(minDp[i-1][j],minDp[i-1][j+1]) + arr[i][j];
}else if( j == 1){
maxDp[i][j] =Math.max(Math.max(maxDp[i-1][j],maxDp[i-1][j+1]),maxDp[i-1][j-1]) + arr[i][j];
minDp[i][j] =Math.min(Math.min(minDp[i-1][j],minDp[i-1][j+1]),minDp[i-1][j-1]) + arr[i][j];
}else{
maxDp[i][j] = Math.max(maxDp[i-1][j],maxDp[i-1][j-1]) + arr[i][j];
minDp[i][j] = Math.min(minDp[i-1][j],minDp[i-1][j-1]) + arr[i][j];
}
}
}
int n = Math.max(Math.max(maxDp[N - 1][0], maxDp[N - 1][1]), maxDp[N - 1][2]);
int m = Math.min(Math.min(minDp[N - 1][0], minDp[N - 1][1]), minDp[N - 1][2]);
System.out.println(n + " " +m);
}
}