BOJ - 2096 내려가기

2096 내려가기 : https://www.acmicpc.net/problem/2096

---

Problem

---

Solve

각 좌표(i,j)에서 배열의 범위를 벗어나지 않는 선에서 (i+1,j-1), (i+1,j), (i+1,j+1)에 있는 값과의 합을 통해 구할 수 있는 최소값과 최대값을 구해야한다.

valueMap = new int[N][N][2]인 3차원 배열을 통해 배열의 아래부분 부터 3가지 방향의 합 중 최소값을 valueMap[i][j][0], 최대값을 valueMap[i][j][1]에 저장하여 첫번째 행까지 반복 해준 후 최소값은 valueMap[0][j][0]의 값 중 최소값을, 최대값은 valueMap[0][j][1]의 값 중 최대값을 반환해주면 된다.

3
1 2 3
4 5 6
4 9 0 을 예로 들어보면

(1,0)의 4는 4,9와 합을 구할 수 있다. 그 중 최소값은 8, 최대값은 13이 되므로 valueMap[1][0][0] = 8, valueMap[1][0][1] = 13으로 갱신한다.

(1,1)의 5는 4,9,0과의 합을 구할 수 있다. 그 중 최소값은 5, 최대값은 14가 valueMap[1][1][0] = 5, valueMap[1][1][1] = 14로 갱신한다.

이를 반복하면 첫번째 행에는 각 열에서 출발 했을때 얻을 수 있는 최대,최소 값을 가지고 있게 된다. 그 중 첫번째 행에서의 최소값은 6,7,8중 6이되고, 최대값은 15,17,18중 18이 되므로 18과 6을 반환하면 된다.

---

Code

public class 내려가기 {
	static int N;
	static int[][] map;
    //현재 열 기준, 왼쪽 아래, 아래, 오른쪽 아래
	static int[] dx = {-1, 0, 1};
	static int max;
	static int min;
	static int[][][] valueMap;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(br.readLine());
		map = new int[N][3];
		valueMap = new int[N][3][2];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < 3; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				valueMap[i][j][0] = valueMap[i][j][1] = map[i][j];
			}
		}

		max = 0;
		min = Integer.MAX_VALUE;
		dp();

		StringBuilder sb = new StringBuilder();
		sb.append(max);
		sb.append(" ");
		sb.append(min);
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	static void dp() {
		for (int i = N - 2; i >= 0; i--) {
			for (int j = 0; j < 3; j++) {
				int minValue = Integer.MAX_VALUE;
				int maxValue = 0;
				for(int d=0;d<3;d++){
					int nx = j+dx[d];
                    //다음 행에서 비교할 3개의 열 중 배열 범위에 들어있는 값과 합할 수 있다.
					if(nx>=0 && nx<3){
                    	//최소값은 다음 행에서 가지는 최소값과의 합
                        //최대값은 다음 행에서 가지는 최대값과의 합
						int minSum = map[i][j] + valueMap[i+1][nx][0];
						int maxSum = map[i][j] + valueMap[i+1][nx][1];
						minValue = Math.min(minValue, minSum);
						maxValue = Math.max(maxValue, maxSum);
					}
				}

				//3개의 값과 비교했을 때 가장 작은값과 큰값 저장
				valueMap[i][j][0] = minValue;
				valueMap[i][j][1] = maxValue;
			}
		}
        //첫번째 행에서의 가장 큰값과 가장 장은 값을 반환한다.
		max = Math.max(Math.max(valueMap[0][0][1], valueMap[0][1][1]), valueMap[0][2][1]);
		min = Math.min(Math.min(valueMap[0][0][0], valueMap[0][1][0]), valueMap[0][2][0]);
	}
}

---

Result

---

Reference