[백준] 내려가기 2096 - java

https://www.acmicpc.net/problem/2096

2096번: 내려가기

public class 내려가기 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int cur[] = new int[3];
		int prevMax[] = new int[3];
		int prevMin[] = new int[3];
		int tempMax[] = new int[3];
		int tempMin[] = new int[3];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int j = 0; j < 3; j++) {
			prevMax[j] = Integer.parseInt(st.nextToken());
		}
		prevMin = prevMax.clone();
		for (int i = 1; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 3; j++) {
				cur[j] = Integer.parseInt(st.nextToken());
			}
			tempMax = prevMax.clone();
			tempMin = prevMin.clone();
			
			prevMax[0] = cur[0] + Math.max(tempMax[0], tempMax[1]);
			prevMax[1] = cur[1] + Math.max(tempMax[2], Math.max(tempMax[0], tempMax[1]));
			prevMax[2] = cur[2] + Math.max(tempMax[1], tempMax[2]);

			prevMin[0] = cur[0] + Math.min(tempMin[0], tempMin[1]);
			prevMin[1] = cur[1] + Math.min(tempMin[2], Math.min(tempMin[0], tempMin[1]));
			prevMin[2] = cur[2] + Math.min(tempMin[1], tempMin[2]);
			
		}

		Arrays.sort(prevMax);
		Arrays.sort(prevMin);

		System.out.println(prevMax[2] + " " + prevMin[0]);
	}
}

메모리 제한이 4MB라서 3*10만의 배열을 여러개 만들면 메모리 초과가 납니다.

그래서 현재 행과 이전 행의 값만으로 연산해야합니다.

1. 처음 행의 값을 받습니다.

2. 최댓값을 구할 때는 현재 행과 이전 행에서 올 수 있는 최댓값을 더해줍니다. 

3. 최솟값도 같이 구해줍니다.

 

처음에 prevMax[0] = cur[0] + Math.max(prevMax[0], prevMax[1]);로 코드를 짰었는데

prevMax가 갱신되어 다음 연산에서 의도치 않은 값이 나와

tempMax를 두어 연산했습니다.

 

슬라이딩 윈도우 + DP 문제였습니다.