[ Baekjoon ][JAVA][2042] 내려가기

www.acmicpc.net/problem/2096

2096번: 내려가기

문제

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

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

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

입력

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

출력

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

에제 입력

예제 출력

접근

처음 언뜻 보기엔 DP로 보였다. 하지만 메모리 제한이 매우 작았고 키포인트는 슬라이딩 윈도우로 푸는 것이었다. 즉 i-1행의 문제들의 결과를 갖고 있는 배열을 이용해 max, min 배열에 현재 i행의 문제들을 풀어서 저장하는 방법이다.
이렇게 해서 배열에 남겨진 제일 마지막 행에 관해서 출력해주면된다.

시간복잡도는 여전히 O(N)이지만 공간복잡도가 O(1)이 되는 엄청난 파워!

코드

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

public class GoingDown_2096 {
	static int[][] d = new int[100001][3];
	static int[][] map = new int[1000001][3];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());

		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			map[i][0] = Integer.parseInt(st.nextToken());
			map[i][1] = Integer.parseInt(st.nextToken());
			map[i][2] = Integer.parseInt(st.nextToken());
		}
		// 메모이제이션 0번째
		d[1][0] = map[1][0];
		d[1][1] = map[1][1];
		d[1][2] = map[1][2];
		
		// max 점화식
		for(int i=2; i<=N; i++) {
			d[i][0] = map[i][0] + Math.max(d[i-1][0], d[i-1][1]);
			d[i][1] = map[i][1] + Math.max(d[i-1][0], Math.max(d[i-1][1], d[i-1][2]));
			d[i][2] = map[i][2] + Math.max(d[i-1][1], d[i-1][2]);
		}
		
		int max = Math.max(d[N][0], Math.max(d[N][1], d[N][2]));
		
		// min 점화식
		for(int i=2; i<=N; i++) {
			d[i][0] = map[i][0] + Math.min(d[i-1][0], d[i-1][1]);
			d[i][1] = map[i][1] + Math.min(d[i-1][0], Math.min(d[i-1][1], d[i-1][2]));
			d[i][2] = map[i][2] + Math.min(d[i-1][1], d[i-1][2]);
		}
		
		int min = Math.min(d[N][0], Math.min(d[N][1], d[N][2]));
		
		System.out.println(max + " " + min);
	}

}