[백준] G4 2096번 내려가기 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

2096번: 내려가기

[문제] 

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

[입력]

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

[출력]

첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

 

 

---

[풀이]

1. 메모리 제한이 4MB이기 때문에 dp처리를 하더라도 2차원 배열을 쓰게 되면 메모리 초과가 발생할 수 있다.

2. 이를 해결해 주기 위해서 1차원 배열로 처리를 한다.

3. 각 칸에 오기 위해서 필요한 최소값과 최댓값을 구하기 위해선 현재 칸의 값과 이전 칸의 값이 필요하다.

4. dp 배열에는 이전 칸의 값을 넣어주고 map에는 현재 칸의 값을 넣어준다.

5. 각 칸에 들어오게 되는 최소, 최대 값을 dp 배열에 넣어준다.

6. 마지막까지 반복을 한다.

7. 마지막에는 dp 배열의 0~2번의 값 중 최소, 최대를 구해서 출력해준다.

[접근]

1. 메모리 제한이 작기 때문에 dp를 처리하면서 어떻게 메모리 제한을 맞출 수 있을까?를 생각하였다.

>> dp배열을 2차원이 아닌 1차원으로 처리하였다.

2. 1, 2, 3번째 칸에 들어오기 위해서는 어떻게 처리해야할까?를 생각하였다.

>> 1번째 : 현재 1번의 값 + 이전 1, 2번 중 최소, 최대 값

>> 2번째 : 현재 2번의 값 + 이전 1, 2, 3번 중 최소, 최대 값

>> 3번째 : 현재 3번의 값 + 이전 2, 3번 중 최소, 최대 값

[코드]

package BOJ_gold;

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

public class Main_G4_2096 {
	static int n;
	static int[] map;
	static int[] dpMax;
	static int[] dpMin;
	static int max = 0;
	static int min = Integer.MAX_VALUE;
	
	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		
		// 0, 1, 2번째를 나타냄.
		dpMax = new int[3];	// 최댓값 DP
		dpMin = new int[3];	// 최솟값 DP
		map = new int[3]; // 2차원 배열로 하려고 했지만 사용 가능 메모리가 작기때문에 1차원 배열로 했다.
		
		for(int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			// 한 줄씩 입력받아서 처리
			for(int j = 0; j < 3; j++) {
				int m = Integer.parseInt(st.nextToken());
				map[j] = m;
			}
			
			// 맨 처음 값들을 입력해주기
			if(i == 0) {
				dpMax[0] = dpMin[0] = map[0];
				dpMax[1] = dpMin[1] = map[1];
				dpMax[2] = dpMin[2] = map[2];
				continue;
			}
			
			// dp의 0번지와 1번지에 값을 바로 넣어서 dp[2]에 값이 이상해짐
			// 그걸 막기 위한 변수
			int max0 = dpMax[0];
			int min0 = dpMin[0];
			
			int max1 = dpMax[1];
			int min1 = dpMin[1];
			
			// 해당 칸 마다 올수있는 최대 값 구하기
			// [n]에는 현재 값 + 이전에 올수 있는 곳들 중 큰 값이 와야한다.
			// 0일 경우 0과 1에서 올 수 있고
			// 1일 경우 0과 1과 2에서 올 수 있고
			// 2일 경우 1과 2에서 올 수 있다.
			// 이건 최소값도 마찬가지이기 때문에 똑같은 로직으로 처리한다.
			dpMax[0] = map[0] + Math.max(dpMax[0], dpMax[1]);
			dpMax[1] = map[1] + Math.max(max0, Math.max(dpMax[1], dpMax[2]));
			dpMax[2] = map[2] + Math.max(max1, dpMax[2]);
			
			// 해당 칸 마다 올수있는 최소 값 구하기			
			dpMin[0] = map[0] + Math.min(dpMin[0], dpMin[1]);
			dpMin[1] = map[1] + Math.min(min0, Math.min(dpMin[1], dpMin[2]));
			dpMin[2] = map[2] + Math.min(min1, dpMin[2]);
		}
		
		// 마지막까지 돌면 각 칸에 올 때의 최대 값을 들고온다.
		// 그 중에서 최고를 구한다.
		for(int i = 0; i < 3; i++) {
			max = Math.max(max, dpMax[i]);
		}
		
		// 마지막까지 돌면 각 칸에 올 때의 최소 값을 들고온다.
		// 그 중에서 최소를 구한다.
		for(int i = 0; i < 3; i++) {
			min = Math.min(min, dpMin[i]);
		}
		
		System.out.println(max + " " + min);
	}
}