[백준] 2096 - 내려가기

[문제링크]

2096번: 내려가기

 

0. 직전 단계의 결과 중 최소 / 최대값만을 취하는 간단한 DP

 

1. 메모리 제한이 작으므로 직전 단계만을 저장하도록 2칸의 배열을 잡는다

 

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = pint(br.readLine());
		int[][]max = new int[2][3];
		int[][]min = new int[2][3];
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n1 = pint(st.nextToken());
			int n2 = pint(st.nextToken());
			int n3 = pint(st.nextToken());
			
			max[1][0]=n1 + Math.max(max[0][0], max[0][1]);
			min[1][0]=n1 + Math.min(min[0][0], min[0][1]);
			
			max[1][1]=n2 + Math.max(max[0][0], Math.max(max[0][1], max[0][2]));
			min[1][1]=n2 + Math.min(min[0][0], Math.min(min[0][1], min[0][2]));
			
			max[1][2]=n3 + Math.max(max[0][1], max[0][2]);
			min[1][2]=n3 + Math.min(min[0][1], min[0][2]);
			
			for (int j = 0; j < 3; j++) {
				max[0][j]=max[1][j];
				min[0][j]=min[1][j];
			}
		}
		System.out.println(Math.max(max[1][0], Math.max(max[1][1], max[1][2]))+" "+
				Math.min(min[1][0], Math.min(min[1][1], min[1][2])));
		
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면