백준 2096 내려가기 (Java)

1. 문제 링크

2096번: 내려가기

 

2. 문제 및 입출력예제

 

3. 문제 풀이

메모리 제한이 있어서 최대한 입력받으면서 풀려고 했다.

처음 입력받은 줄을 배열에 저장한다.

비교 범위에 있는 값들 중 큰 값과 입력받은 값을 더해 저장한다.

저장된 값들 중 최솟값과 최댓값을 찾는다.

 

++++

최솟값과 최댓값을 찾기 위한 배열을 따로 만들어야 했다.

최댓값이나 최솟값을 찾는 과정에서 비교하고 더하는 값의 위치를 잘못 생각했었다. 손으로 그리면서 확인할 때는 다음 줄의 값들과 비교했는데 그렇게 하니까 이상한 값이 나왔다. 다시 저장되는 값들을 확인해보니까 입력받은 값에서 전에 저장된 값들 중 비교해서 더하는 순서였다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new java.io.InputStreamReader(System.in));
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		
		int N = Integer.parseInt(br.readLine());
		int[] line = new int[3]; //입력받는 한 줄
		int[] maxA = new int[3]; //최댓값 구할 배열
		int[] minA = new int[3]; //최솟값 구할 배열
		int[] now = new int[3];
		
		String[] split = new String[3];
		for(int i=0;i<N;i++) {
			split = br.readLine().split(" ");
			for(int j=0;j<3;j++) {
				line[j] = Integer.parseInt(split[j]); 
			}
			
			if(i==0) { //첫 줄
				maxA[0] = line[0];
				maxA[1] = line[1];
				maxA[2] = line[2];
				
				minA[0] = line[0];
				minA[1] = line[1];
				minA[2] = line[2];
			}
			else { 
				now[0] = line[0] + Math.max(maxA[0], maxA[1]);
				now[1] = line[1] + Math.max(maxA[0], Math.max(maxA[1], maxA[2]));
				now[2] = line[2] + Math.max(maxA[1], maxA[2]);
				
				maxA[0] = now[0];
				maxA[1] = now[1];
				maxA[2] = now[2];
				
				now[0] = line[0] + Math.min(minA[0], minA[1]);
				now[1] = line[1] + Math.min(minA[0], Math.min(minA[1], minA[2]));
				now[2] = line[2] + Math.min(minA[1], minA[2]);

				minA[0] = now[0];
				minA[1] = now[1];
				minA[2] = now[2];
			}
		}
		
		max = Math.max(maxA[0], Math.max(maxA[1], maxA[2]));
		min = Math.min(minA[0], Math.min(minA[1], minA[2]));
		System.out.println(max+" "+min);
	}	
}