[백준] 2096번 : 내려가기 - 자바(JAVA)

https://www.acmicpc.net/problem/2096

2096번: 내려가기

 

문제 해석

N 줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다.

이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 된다.

먼저 처음 세 개의 숫자 중에서 하나를 골라서 시작한다.

다음 줄로 내려갈 떄는 바로 아래의 수로 넘어가거나, 바로 아래의 수와 붙어있는 수로만 이동할 수 있다.

숫자 표가 주어져 있을 때 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성해라.

점수는 이동한 곳의 수의 합이다.

 

https://www.acmicpc.net/problem/2096

만약 별표가 현재 위치라고 가정했을 때, 파란 동그라미는 다음 줄로 이동할 수 있는 위치들입니다.

X 표시는 내려갈 수 없는 위치들입니다.

 

문제 풀이 전 설계

우선 모든 경우의 수를 탐색했을 때 3^100,000에 육박하는 경우가 나올 것 같아 완전 탐색은 불가능합니다. 

또한 가장 큰 수를 뽑는 Greedy 방식을 가정했을 때 지금 한 선택이 최선이 아닐 수도 있습니다.

 

정말 극단적으로 다음과 같은 게임보드가 제공된다면 Greedy 방식은 어떻게 될까요?

4	1	9
9	2	1

 

처음에 가장 큰 수인 9로 이동합니다.

그다음 이동할 수 있는 경우인 1, 2 사이에서 2를 선택하면 총 11입니다.

 

하지만 13을 선택하는 경우가 가장 큰 경우의 수입니다. (문제가 발생합니다)

 

하지만 가운데에 있는 수를 선택했을 때는 조금 특별합니다.

가운데에 있는 수가 가장 크다면/작다면  이를 선택하지 않을 이유가 없습니다.

 

가운데 수를 선택했을 때는 다음 선택지가 3개가 존재하지만 왼쪽/오른쪽수를 선택한다면 선택지가 2개밖에 존재하지 않습니다.

 

따라서 왼쪽/오른쪽을 선택하는 경우에는 문제가 발생할 수 있습니다.

 

다음의 예시로 살펴보겠습니다.

5	2	6
5	2	9
9	1	2
1	3	2
1	3	9

1. 가운데 수가 가장 큰 경우에는 가운데 수를 선택합니다. ( 가운데 수가 가장 크지 않습니다)

2. 가운데 수가 가장 크지 않은 경우에는 오른쪽, 왼쪽수를 선택해야 합니다.

3. 만약 왼쪽(5)을 선택한다면 다음에 올 수 있는 후보는 5와 2입니다.

4. 만약 오른쪽(6)을 선택한다면 다음에 올 수 있는 후보는 9와 2입니다.

 

지금 왼쪽을 선택했을 때의 최선은 10이고 오른쪽을 선택했을때의 최선은 15입니다.

그렇다면 지금 오른쪽 선택하는 게 옳을까요?

 

다음 상황까지 보았을 때 왼쪽을 선택하는 경우에는 9, 1라는 선택지가 존재합니다.

따라서 합은 19입니다.

 

오른쪽을 선택하는 경우에는 1, 2라는 선택지가 존재합니다.

따라서 합은 17입니다.

 

따라서 Greedy는 불가능해 보입니다(가운데 수가 최대인 경우는 가능)

 

1. 가운데 수가 가장 큰 경우에는 가운데 수를 선택합니다.

2. 가운데 수가 가장 크지 않은 경우에는 왼쪽 또는 오른쪽 수를 선택합니다.

3. 이를 재귀적으로 반복한다면 최악의 경우 스택이 100,000개가 쌓일 텐데 가능할까요..?

 

 

DP, 메모이제이션으로 해결할 수 있을까요?

우선 메모리 제한은 4MB가 아니라 256MB입니다.

 

https://mygumi.tistory.com/143

계속 가운데를 선택했을 때, 왼쪽, 오른쪽을 선택했을 때를 구분지어서 생각해보았는데 너무 Greedy 적으로 생각해서 이렇게 간단하게 해결이 되는걸 못 찾아서 아쉬웠습니다.

 

문제를 해결하기 위해서 필요한 것은 이것이 전부입니다.

DP [N][3]을 선언하며 DP [N][3]은 N번째 줄에서 각 인덱스를 선택했을 때의 최댓값을 기록합니다.

 

하지만 현재 값을 경신하기 위해서는 이전 값들의 최댓값/최솟값만 기록해주면 되는데 굳이 N개의 정보들을 모두 기록할 필요가 없습니다.

 

따라서 하나의 최대/최솟값을 구하기 위해서는 DP [2][3]의 배열만 필요합니다.

 

maxDP를 기준으로 최댓값을 찾는 것을 예시로 들어보겠습니다.

maxDP[1][0] = Math.max(maxDP[0][0], maxDP[0][1]) + firstValue;

여기서 maxDP [1][0]은 첫 번째를 선택했을 때 최댓값이 메모이제이션됩니다.

여기서 maxDP [0][0]은 파란색 첫 번째 값을 의미합니다.

여기서 maxDP [0][1]은 파란색 두 번째 값을 의미합니다.

여기서 firstValue는 검은색 첫번째값을 의미합니다.

 

즉, 검은색 첫번째값의 최댓값을 구하기위해서는 파란색 첫번째, 두번째값중 최대를 선택하여 검정색의 값을 더하면 됩니다.

 

maxDP[1][1] = Math.max(Math.max(maxDP[0][0], maxDP[0][1]), maxDP[0][2]) + secondValue;

위와 비슷한 로직으로 요약해보겠습니다.

검은색 두번째값의 최댓값을 구하기 위해서는 파란색 첫번째, 두번째값, 세번째값중 최대를 선택하여 해당 검정색 값을 더해라입니다.

 

maxDP[1][2] = Math.max(maxDP[0][1], maxDP[0][2]) + thirdValue;

검은색 세번째값의 최댓값을 구하기 위해서는 두번째값, 세번째값중 최대를 선택하여 해당 검정색 값을 더해라입니다.

 

이렇게 반복하게 되면 최종적으로 maxDP에 최댓값들이 기록됩니다.

 

minDP는 반대로 최솟값들을 기록하기 위해 Math.min() 메서드를 이용하면 됩니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_2096_내려가기 {

	static final int NUMBER_COUNT = 3;
	static int min,max;
	static int[][] maxDP;
	static int[][] minDP;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = null;

		// DP[2][3] = 이전줄과 현재줄의 값을통해 0,1,2번째 index를 선택했을때의 최소를 메모이제이션
		maxDP = new int[2][3];
		minDP = new int[2][3];

		// 초기화
		st = new StringTokenizer(br.readLine());
		for (int j = 0; j < NUMBER_COUNT; j++) {
			int tempValue = Integer.parseInt(st.nextToken());
			maxDP[0][j] = tempValue;
			minDP[0][j] = tempValue;
		}
		//만약 N=1이라면 아래 for문이 실행되지 않기 때문에 미리 max,min 값 계산
		max= Math.max(Math.max(maxDP[0][0], maxDP[0][1]), maxDP[0][2]);
		min = Math.min(Math.min(minDP[0][0], minDP[0][1]), minDP[0][2]);
		
        	//반복문 실행하며 max,min 값 갱신
		for (int i = 1; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int firstValue = Integer.parseInt(st.nextToken()); 
			int secondValue = Integer.parseInt(st.nextToken()); 
			int thirdValue = Integer.parseInt(st.nextToken());
			
			//find maxDP
			maxDP[1][0] = Math.max(maxDP[0][0], maxDP[0][1]) + firstValue; 
			maxDP[1][1] = Math.max(Math.max(maxDP[0][0], maxDP[0][1]),maxDP[0][2]) + secondValue; 
			maxDP[1][2] = Math.max(maxDP[0][1], maxDP[0][2]) + thirdValue; 
			
			
			
			//find minDP
			minDP[1][0] = Math.min(minDP[0][0], minDP[0][1]) + firstValue;
			minDP[1][1] = Math.min(Math.min(minDP[0][0], minDP[0][1]), minDP[0][2]) + secondValue;
			minDP[1][2] = Math.min(minDP[0][1], minDP[0][2]) + thirdValue;			
			
			max= Math.max(Math.max(maxDP[1][0], maxDP[1][1]), maxDP[1][2]);
			min = Math.min(Math.min(minDP[1][0], minDP[1][1]), minDP[1][2]);
			
            		//다음 for문을 위한 값 덮어쓰기
			maxDP[0][0] = maxDP[1][0];
			maxDP[0][1] = maxDP[1][1];
			maxDP[0][2] = maxDP[1][2];
			
			minDP[0][0] = minDP[1][0];
			minDP[0][1] = minDP[1][1];
			minDP[0][2] = minDP[1][2];
		}
		
		System.out.println(max + " " + min);

	}
	
}