2096번: 내려가기
첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.
www.acmicpc.net
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);
}
}
