BOJ_2096 : 내려가기

👉 문제링크

2096번: 내려가기

---

---

🔸 문제 분석 🔸

• N * 3 보드판을 내려가며 최대,최소값을 구하는 문제이다.
• 내려갈 수 있는 방법이 3가지가 있는데, 브루트포스로 그래프 탐색하면 시간초과가 난다.
• 내려가는 방법이 아닌, 역으로 이전 줄을 보고 최대/최소값을 고르는 DP 방식으로 풀이할 수 있다.

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = null;

		int N = Integer.parseInt(br.readLine());
		int[][] map = new int[N + 1][3];
		int[][][] dp = new int[N + 1][3][2];

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

		int[][] dy = {{0, 1}, {-1, 0, 1}, {-1, 0}};

		int max, min;
		for (int i = 1; i <= N; i++) {
			for (int j = 0; j < 3; j++) {
				max = 0;
				min = Integer.MAX_VALUE;
				for (int k = 0; k < dy[j].length; k++) {
					max = Math.max(max, dp[i - 1][j + dy[j][k]][0]);
					min = Math.min(min, dp[i - 1][j + dy[j][k]][1]);
				}
				dp[i][j][0] = max + map[i][j];
				dp[i][j][1] = min + map[i][j];
			}
		}

		max = 0;
		min = Integer.MAX_VALUE;
		for (int i = 0; i < 3; i++) {
			max = Math.max(max, dp[N][i][0]);
			min = Math.min(min, dp[N][i][1]);
		}
		sb.append(max).append(' ').append(min);

		bw.write(sb.toString());
		bw.flush();
	}
}

🔸 코드 해석 🔸

• 보드판의 가중치 정보를 입력받고, 내려가는 3가지 방법에 대해 dy에 저장했다.
  (실제로는 올려다보는 방식으로 사용했다)
• N줄을 하나씩 내려가며 계산을 반복한다.
  • 가로 3칸을 기준으로 이전 줄에서 올 수 있는 값의 최대/최소값을 구한다.
  • 구한 각 칸의 최대/최소값 + 해당 칸의 보드판 가중치를 저장한다.
• 가장 아래줄에서 최대/최소값을 구해 출력한다.

---

🔸 end 🔸

• 처음엔 DFS + 메모이제이션으로 접근했는데 시간초과가나서 질문을 참고해 DP로 변경했다.
  • 코테를 오랜만에 풀어서 간단한 DP인데 생각하지 못한 것 같다.
• 문제태그에 슬라이딩윈도우가 있는데, 내가 아는 방식의 플이가 따로 있는게 아니라서 무슨 뜻일까 찾아보았다.
  • dp에서 테이블을 재활용하면서 메모리를 아끼는 (흔히 토글링이라고도 불리는) 테크닉을 슬라이딩 윈도우라고 부리도 한다고 한다. (질문)