[BOJ] 백준 2096 - 내려가기 풀이

1. 문제

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

2096번: 내려가기

 

2. 풀이 Point

• 각 행 별로 선택할 수 있는 경우의 수는 세 가지다. (첫 번째, 두 번째, 세 번째)
• 그리고 각 경우의 수를 선택했을 때 다음을 고를 경우의 수는 세 가지이다.
• 따라서 0번 열, 1번 열, 2번 열을 각각 메모이제이션 해주어야 하므로 dp를 2차원 배열로 만든다.
• 각 경우의 수를 골랐을 때의 최대 값은 다음과 같은 형식으로 식을 세울 수 있다.

• 최소 값도 이와 마찬가지로 N - 1까지 계산한 후 3가지 경우에 대해 최대 값, 최소 값을 구하면 정답!!
  
  
  

3. 소스 코드

// 첫 번째 : 최대 최소를 각각 나눠서 처리하기
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

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

				// 최대 구하기
        int[][] dp = new int[N][3];
        dp[0][0] = map[0][0];
        dp[0][1] = map[0][1];
        dp[0][2] = map[0][2];

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

        String maxResult = Integer.toString(Math.max(dp[N - 1][0] , Math.max(dp[N - 1][1], dp[N - 1][2]))); // 최대 값

				// 최소 구하기
        dp = new int[N][3];
        dp[0][0] = map[0][0];
        dp[0][1] = map[0][1];
        dp[0][2] = map[0][2];
        for (int i = 1; i < N; i++) {
            dp[i][0] += map[i][0] + Math.min(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] += map[i][1] + Math.min(Math.min(dp[i - 1][0], dp[i - 1][1]), dp[i - 1][2]);
            dp[i][2] += map[i][2] + Math.min(dp[i - 1][1], dp[i - 1][2]);
        }

        String minResult = Integer.toString(Math.min(dp[N - 1][0] , Math.min(dp[N - 1][1], dp[N - 1][2]))); // 최소 값

        bw.write(maxResult + " " + minResult);
        bw.flush();
        bw.close();
        br.close();
    }
}

// 두 번째 : 한 번에 처리하기
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

    static class MaxMinObject {
        int max;
        int min;

        public MaxMinObject(int max, int min) {
            this.max = max;
            this.min = min;
        }
    }

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

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

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

        MaxMinObject[][] dp = new MaxMinObject[N][3];
        dp[0][0] = new MaxMinObject(map[0][0], map[0][0]);
        dp[0][1] = new MaxMinObject(map[0][1], map[0][1]);
        dp[0][2] = new MaxMinObject(map[0][2], map[0][2]);

        for (int i = 1; i < N; i++) {
            dp[i][0] = new MaxMinObject(map[i][0] + Math.max(dp[i - 1][0].max, dp[i - 1][1].max),
                    map[i][0] + Math.min(dp[i - 1][0].min, dp[i - 1][1].min));
            dp[i][1] = new MaxMinObject(map[i][1] + Math.max(Math.max(dp[i - 1][0].max, dp[i - 1][1].max), dp[i - 1][2].max),
                    map[i][1] + Math.min(Math.min(dp[i - 1][0].min, dp[i - 1][1].min), dp[i - 1][2].min));
            dp[i][2] = new MaxMinObject(map[i][2] + Math.max(dp[i - 1][1].max, dp[i - 1][2].max),
                    map[i][2] + Math.min(dp[i - 1][1].min, dp[i - 1][2].min));
        }

        bw.write(Math.max(dp[N - 1][0].max, Math.max(dp[N - 1][1].max, dp[N - 1][2].max)) + " " + Math.min(dp[N - 1][0].min, Math.min(dp[N - 1][1].min, dp[N - 1][2].min)));
        bw.flush();
        bw.close();
        br.close();
    }
}

4. 배운점

1. 시간이 넉넉하다면 머리속으로 떠오르는 생각 그대로 작성하는 것도 좋은 방법이다.
   
   
   

5. 점수

90/100