[BOJ] 2096 내려가기 - JAVA

1. 문제

2096번: 내려가기

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

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

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

---

2. 풀이

min[0]은 이전 값, min[1]은 현재값을 저장한다. max 배열도 동일하다.

먼저 min[1]과 max[1]에 입력받은 수를 저장한다.

[1][0]은 윗줄의 첫번째, 두번째 칸 중에서 골라야 한다. 골라서 min[1][0]에 더한다.

[1][1]은 윗줄 전부에서 골라야 한다. 

[1][2]는 윗줄 두번째, 세번째 칸 중에서 골라서 min[1][2]에 더한다.

입력과 탐색이 다 끝났다면 첫번째 줄 중 가장 작은 값, 가장 큰 값을 골라 출력한다.

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

public class BOJ_2096_내려가기2 {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
		int[][] min = new int[2][3];
		int[][] max = new int[2][3];

		StringTokenizer st;
		for(int i=1;i<=N;i++){
			st = new StringTokenizer(in.readLine());
			for(int j=0;j<3;j++){
				min[1][j] = max[1][j] = Integer.parseInt(st.nextToken());
			}

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

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

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

			for(int j=0;j<3;j++){
				min[0][j] = min[1][j];
				max[0][j] = max[1][j];
			}
		}

		int ans1 = Math.max(max[0][0], Math.max(max[0][1], max[0][2]));
		int ans2 = Math.min(min[0][0], Math.min(min[0][1], min[0][2]));

		System.out.println(ans1 +" "+ ans2);
	}
}

---

3. 결과

[N][3]칸 배열을 만들어서 dp로 했더니 메모리를 가장 많이 썼다.

자바는 해당되지 않지만 다른 언어는 메모리 4MB제한이라 조금 더 적게 사용할 수 있는 방법이 뭘지 생각해보다가 두 가지 배열을 가지고 스위칭해가면서 푸는 방식을 발견했다.

위의 세 풀이가 전부 그런 식인데 엄청나게 큰 차이가 나진 않는다. (입력하는 데 이미 메모리를 많이 소비해서 그럴까?)