[백준] 알고리즘 분류(다이나믹 프로그래밍,JAVA)2096번, 내려가기

문제 링크

2096번: 내려가기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 내려가는 위치에 따라 다음 줄에 내려갈 때 제약이 걸립니다.

2. 숫자는 0 ~ 9 중 하나가 주어집니다.

3. 처음에서 맨 아래로 내려갈 때 최대 점수와 최소 점수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 내려갈 때 얻을 수 있는 점수의 최대값은 maxDP[][], 최소값은 minDP[][]에 저장합니다.

 

3. minDP, maxDP에 최소값, 최대값을 결과로 출력합니다.

 

내려가기 DP탐색!

 

내려갈 때 행동을 취하는 3가지 경우

 

1. 왼쪽으로 내려가기! (오른쪽으로 내려왔을 때 불가능!)

2. 중앙으로 내려가기!

3. 오른쪽으로 내려가기! (왼쪽으로 내려왔을 때 불가능!)

 

탐색과정!

 

DP[3][N] 배열을 통해서 각 경우의 최대값을 저장합니다.

 

DP[0][i] : i번째 열에서 1번 행동(왼쪽으로 내려가기)를 진행했을 때 최대값, 최소값

DP[1][i] : i번째 열에서 2번 행동(중앙으로 내려가기)를 진행했을 때 최대값, 최소값

DP[2][i] : i번째 열에서 3번 행동(오른쪽으로 내려가기)를 진행했을 때 최대값, 최소값

 

maxDP[][] 계산 점화식!

 

maxDP[0][i] :  Math.max(maxDP[0][i-1], maxDP[1][i-1]) + i번째 왼쪽 점수

해석 : 

왼쪽으로 내려오려면, 이전에 1번, 2번 행동을 진행해야합니다.

그래서 이전에 1번과 2번 행동을 했던 값 중 큰 값에 현재 왼쪽 점수를 더한 값이  최대값입니다.

 

maxDP[1][i] :  Math.max(maxDP[0][i-1], Math.max(maxDP[1][i-1], maxDP[2][i-1])) + i번째 중앙 점수

해석 :

중앙으로 내려오려면, 이전에 1번, 2번, 3번 행동을 진행해야합니다.

그래서 이전에 1번, 2번, 3번 행동을 했던 값 중 큰 값에 현재 중앙 점수를 더한 값이  최대값입니다.

 

maxDP[2][i] :  Math.max(maxDP[1][i-1], maxDP[2][i-1]) + i번째 오른쪽 점수

오른쪽으로 내려오려면, 이전에 2번, 3번 행동을 진행해야합니다.

그래서 이전에 2번과 3번 행동을 했던 값 중 큰 값에 현재 오른쪽 점수를 더한 값이  최대값입니다.

 

minDP[][] 계산 점화식!

 

minDP[0][i] :  Math.min(minDP[0][i-1], minDP[1][i-1]) + i번째 왼쪽 점수

해석 : 

왼쪽으로 내려오려면, 이전에 1번, 2번 행동을 진행해야합니다.

그래서 이전에 1번과 2번 행동을 했던 값 중 작은 값에 현재 왼쪽 점수를 더한 값이  최소값입니다.

 

minDP[1][i] : Math.min(minDP[0][i-1], Math.min(minDP[1][i-1], minDP[2][i-1])) + i번째 중앙 점수

해석 :

중앙으로 내려오려면, 이전에 1번, 2번, 3번 행동을 진행해야합니다.

그래서 이전에 1번, 2번, 3번 행동을 했던 값 중 작은 값에 현재 중앙 점수를 더한 값이  최소값입니다.

 

minDP[2][i] :  Math.min(minDP[1][i-1], minDP[2][i-1]) + i번째 오른쪽 점수

오른쪽으로 내려오려면, 이전에 2번, 3번 행동을 진행해야합니다.

그래서 이전에  2번과 3번 행동을 했던 값 중 작은 값에 현재 오른쪽 점수를 더한 값이  최소값입니다.

 

예제입력에 설명을 보시면 진행되는 과정을 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 3

 

내려가기 정보

1	2	3
4	5	6
4	9	0

 

2. 내려갈 때 얻을 수 있는 점수의 최대값은 maxDP[][], 최소값은 minDP[][]에 저장합니다.

 

maxDP[] 탐색!

 

	1	2	3
왼쪽	1
중앙	2
오른쪽	3

 

	1	2	3
왼쪽	1	2 + 4 = 6
중앙	2	3 + 5 = 8
오른쪽	3	3 + 6 = 9

 

	1	2	3
왼쪽	1	6	8 + 4 = 12
중앙	2	8	9 + 9 = 18
오른쪽	3	9	9 + 0 = 9

minDP[] 탐색!

 

	1	2	3
왼쪽	1
중앙	2
오른쪽	3

 

	1	2	3
왼쪽	1	1 + 4 = 5
중앙	2	1 + 5 = 6
오른쪽	3	2 + 6 = 8

 

	1	2	3
왼쪽	1	5	5 + 4 = 9
중앙	2	6	5 + 9 = 14
오른쪽	3	8	6 + 0 = 6

 

3. minDP, maxDP에 최소값, 최대값을 결과로 출력합니다.

 

maxDP[][] 최대값

	1	2	3
왼쪽	1	6	12
중앙	2	8	18
오른쪽	3	9	9

 

minDP[][] 최소값

 

	1	2	3
왼쪽	1	5	9
중앙	2	6	14
오른쪽	3	8	6

 

18 6 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 내려가기 점수를 띄어쓰기 기준 나누었습니다.
• 점화식을 통해 minDP[][]와 maxDP[][]의 최대값, 최소값들을 저장합니다.
• minDP[][], maxDP[][]에 최대값과 최소값을 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

결과코드

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        int[][] score = new int[N][3];	//입력되는 점수 저장 배열
        int[][] minDP = new int[3][N];	//최소값 메모이제이션
        int[][] maxDP = new int[3][N];	//최대값 메모이제이션
        //입력되는 점수값 저장!
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<3;j++)
                score[i][j] = Integer.parseInt(st.nextToken());
        }
        //minDP[][], maxDP[][] 초기값 설정!
        minDP[0][0] = maxDP[0][0] = score[0][0];
        minDP[1][0] = maxDP[1][0] = score[0][1];
        minDP[2][0] = maxDP[2][0] = score[0][2];
        //minDP[][], maxDP[][] 점화식을 이용한 값 저장!
        for(int i=1;i<N;i++){
            //maxDP[][] 구성!
            maxDP[0][i] = Math.max(maxDP[0][i-1], maxDP[1][i-1]) + score[i][0];
            maxDP[1][i] = Math.max(maxDP[0][i-1], Math.max(maxDP[1][i-1], maxDP[2][i-1])) + score[i][1];
            maxDP[2][i] = Math.max(maxDP[1][i-1], maxDP[2][i-1]) + score[i][2];

            //minDP[][] 구성!
            minDP[0][i] = Math.min(minDP[0][i-1], minDP[1][i-1]) + score[i][0];
            minDP[1][i] = Math.min(minDP[0][i-1], Math.min(minDP[1][i-1], minDP[2][i-1])) + score[i][1];
            minDP[2][i] = Math.min(minDP[1][i-1], minDP[2][i-1]) + score[i][2];
        }
        //minDP[][]에 최소값, maxDP[][] 최대값 구하기!
        int max = Math.max(maxDP[0][N-1], Math.max(maxDP[1][N-1] , maxDP[2][N-1]));
        int min = Math.min(minDP[0][N-1], Math.min(minDP[1][N-1] , minDP[2][N-1]));
        bw.write(max + " " + min);	//최대값, 최소값 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}