[Baekjoon] 15645_내려가기 2

문제(출처: https://www.acmicpc.net/problem/15645)

---

< 내려가기 2 >

 

문제 풀이 

 

dp를 사용하여 현재 위치에서 바로 위의 수, 바로 위의 수와 붙어있는 수를 살펴보며 최대 점수, 최소 점수를 구한다. 

 

my solution (Java)

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 _15645_ { // 내려가기 2

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

		int n = Integer.parseInt(bf.readLine());

		int arr[][] = new int[n][3];

		int maxDp[][] = new int[n][3];
		int minDp[][] = new int[n][3];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(bf.readLine());

			for (int j = 0; j < 3; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				minDp[i][j] = Integer.MAX_VALUE;
			}
		}

		for (int i = 0; i < 3; i++) {
			maxDp[0][i] = arr[0][i];
			minDp[0][i] = arr[0][i];
		}

		for (int i = 1; i < n; i++) {
			for (int j = 0; j < 3; j++) {
				if (j - 1 >= 0) {
					maxDp[i][j] = Math.max(maxDp[i][j], maxDp[i - 1][j - 1] + arr[i][j]);
					minDp[i][j] = Math.min(minDp[i][j], minDp[i - 1][j - 1] + arr[i][j]);
				}
				if (j + 1 < 3) {
					maxDp[i][j] = Math.max(maxDp[i][j], maxDp[i - 1][j + 1] + arr[i][j]);
					minDp[i][j] = Math.min(minDp[i][j], minDp[i - 1][j + 1] + arr[i][j]);
				}
				maxDp[i][j] = Math.max(maxDp[i][j], maxDp[i - 1][j] + arr[i][j]);
				minDp[i][j] = Math.min(minDp[i][j], minDp[i - 1][j] + arr[i][j]);
			}
		}

		int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
		for (int i = 0; i < 3; i++) {
			max = Math.max(max, maxDp[n - 1][i]);
			min = Math.min(min, minDp[n - 1][i]);
		}

		bw.write(max + " " + min);
		bw.flush();
	}

변수)
n : 입력값 
arr : 게임 점수
maxDp, minDp : 최대 점수, 최소 점수 구하기 위한 배열 
max, min : 최대 점수, 최소 점수 

 

n을 입력받는다. n 줄 만큼 게임 점수를 입력받아 배열 arr에 저장한다. maxDp와 minDp의 0번째 행을 arr 0번째 행으로 초기화하고, 1행 ~ n-1행까지 ([i-1][j-1]에서 내려오기, [i-1][j+1]에서 내려오기, [i-1][j]에서 내려오기) 중에 최댓값과 최솟값을 구해 각 배열에 저장한다. 

 

최종 maxDp와 minDp의 [n-1][i]를 탐색하며 최대 점수와 최소 점수를 구해 출력한다.

---

---