백준 2096 내려가기 with 자바

---

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

풀이

윗 줄에서 부터 최대 / 최소값을 더해가면사 내려가면 된다

 

어떤 위치( [i][j] ) 에서의 최대값은

윗 줄( [i-1][j-1], [i-1][j], [i-1][j+1] ) 중에서 최대값인 녀석을

선택하여 해당 위치( [i][j] ) 에 더해주면 된다

 

예를 들어 배열이

1 2 3

4 5 6

4 9 0 인경우

 

2번째 줄 (4 5 6) 부터 시작하여

4는 윗줄 중에 가장 큰 2,

5는 3,

6은 3 과 더하면

 

6 8 9

4 9 0 이 된다

이제 그 다음 줄 (4 9 0)에서 계산을 하면

4는 윗줄 중에 가장 큰 8,

9는 9,

0은 9 와 더하면

 

결과는 12, 18 ,9 가 되며

최대값은 18이 된다

 

해당 로직을 구현한 코드이다

static int[] dj = {-1, 0, 1};

static boolean isIn(int j) {
    if (j >= 0 && j < 3) return true;
    return false;
}

static void solve(int i) {
    if (i == N - 1) return;

    for (int j = 0; j < 3; j++) {

        int max = 0;
        int min = Integer.MAX_VALUE;
        for (int dir = 0; dir < 3; dir++) {
            int newJ = j + dj[dir];

            if (isIn(newJ)) {
                max = Math.max(max, arrMax[i][newJ]);
                min = Math.min(min, arrMin[i][newJ]);
            }
        }

        arrMax[i + 1][j] += max;
        arrMin[i + 1][j] += min;
    }

    solve(i + 1);
}

i = 0번째 행에서 부터 시작하여

i+1번 행의 각각의 원소에

i번째 행의 최대 / 최소 값을 더해주었으며

재귀를 통해 N-1행 전까지 실행하였다

 

재귀가 끝난 후

마지막 행에서 최대 / 최소 값만 찾아주면 된다

int max = Math.max(Math.max(arrMax[N - 1][0], arrMax[N - 1][1]), arrMax[N - 1][2]);
int min = Math.min(Math.min(arrMin[N - 1][0], arrMin[N - 1][1]), arrMin[N - 1][2]);

 

---

 

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int[][] arrMax;
    static int[][] arrMin;
    static int[] dj = {-1, 0, 1};

    static boolean isIn(int j) {
        if (j >= 0 && j < 3) return true;
        return false;
    }

    static void solve(int i) {
        if (i == N - 1) return;

        for (int j = 0; j < 3; j++) {

            int max = 0;
            int min = Integer.MAX_VALUE;
            for (int dir = 0; dir < 3; dir++) {
                int newJ = j + dj[dir];

                if (isIn(newJ)) {
                    max = Math.max(max, arrMax[i][newJ]);
                    min = Math.min(min, arrMin[i][newJ]);
                }
            }

            arrMax[i + 1][j] += max;
            arrMin[i + 1][j] += min;
        }

        solve(i + 1);
    }

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        arrMax = new int[N][3];
        arrMin = new int[N][3];

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

        solve(0);

        int max = Math.max(Math.max(arrMax[N - 1][0], arrMax[N - 1][1]), arrMax[N - 1][2]);
        int min = Math.min(Math.min(arrMin[N - 1][0], arrMin[N - 1][1]), arrMin[N - 1][2]);

        System.out.println(max + " " + min);
    }
}