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

내려가기

풀이

문제에서 주어지는 조건은 위의 그림과 같이 3개이다. 따라서 3개의 경우에 대해 각각 따로 구현하여 요구하는 값을 구해도 상관없지만 그렇게 푸는 것은 공부하는 의미가 없다고 생각한다.

위의 그림을 잘 보면 규칙을 발견할 수 있다.

현재 위치에 -1, 0, 1 을 더한 값으로 이동할 수 있다는 것이다.

이 규칙을 파악했다면 나머지는 dp로 풀 수 있다.

최대값 찾기만을 따로 보면

for (int i = 1; i < n; i++) {
	for (int j = 0; j < 3; j++) {
		for (int k = 0; k < 3; k++) {
			if (j + d[k] >= 0 && j + d[k] < 3) {
				dpMax[i][j + d[k]] = Math.max(dpMax[i][j + d[k]], dpMax[i - 1][j] + arr[i][j + d[k]]);
			}
		}
	}
}
       

와 같이 구할 수 있다. dp 배열에 값이 쌓이고 최종적으로 마지막 행의 최대값을 구하면 그 값이 문제에서 요구하는 최대값과 같다.

최소값 구하는 것도 마찬가지로 구할 수 있다.

코드

import java.io.*;
import java.util.Arrays;

public class Main {
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static int n, m;
    static int[] d = {-1, 0, 1};

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] first = br.readLine().split(" ");
        n = Integer.parseInt(first[0]);
        int[][] arr = new int[n][3];
        int[][] dpMax = new int[n][3];
        int[][] dpMin = new int[n][3];

        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 0; j < 3; j++) {
                arr[i][j] = Integer.parseInt(line[j]);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++)
                dpMin[i][j] = Integer.MAX_VALUE;
        }

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

        //최대찾기
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    if (j + d[k] >= 0 && j + d[k] < 3) {
                        dpMax[i][j + d[k]] = Math.max(dpMax[i][j + d[k]], dpMax[i - 1][j] + arr[i][j + d[k]]);
                    }
                }
            }
        }

        //최소 찾기
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    if (j + d[k] >= 0 && j + d[k] < 3) {
                        dpMin[i][j + d[k]] = Math.min(dpMin[i][j + d[k]], dpMin[i - 1][j] + arr[i][j + d[k]]);
                    }
                }
            }
        }

        int max = Arrays.stream(dpMax[n - 1]).max().getAsInt();
        int min = Arrays.stream(dpMin[n - 1]).min().getAsInt();

        bw.write(max + " " + min + "\n");
        bw.close();
        br.close();
    }

}