[백준2096] - 내려가기 (JAVA)

[문제]

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

2096번: 내려가기

---

 

[문제풀이 전]

 

문제를 보자마자 정수삼각형 문제가 떠올랐다. 그래서 똑같은 방법으로 접근하여 점화식을 d[i][j] = i, j 지점에 왔을 때 수의 최대, 최소 값 이라고 정하고, 문제에 주어진 조건에 따라 푸니 쉽게 풀렸다. 아마 정수삼각형을 먼저 풀었으면 누구나 쉽게 풀었을 것 같다.

 

---

 

[문제풀이] 

문제에서 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하라 하였으니 이를 토대로 점화식을 세웠다.

d[i][j] = i, j  좌표에서의 최대 점수, 최소 점수 값  이라고 세우고, 최대 점수일 땐 항상 큰 값을 가져가고 최소 점수는 항상 작은 값을 가져가도록 코드를 구현하는데! 문제에 주어진 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 조건을 지켜야한다.

 

항상 세줄씩 주어지기 때문에 d[i][0] , d[i][1], d[i][2] 인 경우로 나눠서 구한다. 그리고 점화식에 의해 d[i-1][0], d[i-1][1], d[i-1][2] 또한 최대, 최소 값을 항상 가져야한다. 그러면 하나만 예를들어 왼쪽 0 인경우 d[i][0] 인 경우는 d[i-1][0], d[i-1][1] 에서 내려왔을 텐데 둘중 최대, 최소값을 가져가도록 하고 현재 위치의 값을 더해서 구현을 하면 된다.

 

---

 

[소스코드] 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[][] map = new int[n + 1][3];
        int[][] maxD = new int[n + 1][3];
        int[][] minD = new int[n + 1][3];

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

        for (int i = 1; i <= n; i++) {
            maxD[i][0] = Math.max(maxD[i - 1][0], maxD[i - 1][1]) + map[i][0];
            maxD[i][1] = Math.max(maxD[i - 1][0], Math.max(maxD[i - 1][1], maxD[i - 1][2])) +  map[i][1];
            maxD[i][2] = Math.max(maxD[i - 1][2], maxD[i - 1][1]) + map[i][2];

            minD[i][0] = Math.min(minD[i - 1][0], minD[i - 1][1]) + map[i][0];
            minD[i][1] = Math.min(minD[i - 1][0], Math.min(minD[i - 1][1], minD[i - 1][2])) +  map[i][1];
            minD[i][2] = Math.min(minD[i - 1][2], minD[i - 1][1]) + map[i][2];
        }

        int maxAns = 0;
        int minAns = Integer.MAX_VALUE;
        for (int i = 0; i < 3; i++) {
            if (maxAns < maxD[n][i]) {
                maxAns = maxD[n][i];
            }

            if (minAns > minD[n][i]) {
                minAns = minD[n][i];
            }
        }

        System.out.print(maxAns + " " + minAns);
    }
}

 

 

 

 

 

 

 

---