[BOJ 2096] 내려가기 (Java, DP, 슬라이딩 윈도우)

 

 

---

문제 링크 

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

2096번: 내려가기

---

문제 풀이 

- 시간 복잡도 O(N)

- 메모리 제한 4MB

 

직접 문제를 풀었을 때 최대 값을 구하는 것은 Bottom-Up방식으로 설명에 따라 그대로 하였기에 구할 수 있었다. 

그러나 최소 값의 경우 구할 수 없었고, 기술 블로그를 찾아 본 결과 '메모리 제한', '슬라이딩 윈도우 기법'와 같은 파악하지 못 한 부분에 대해서도 확인할 수 있었다. (최소값의 경우 반대로 선택 가능 범위 내에 최소 값을 더해 갱신해주는 형태였다 하하..)

 

 

초기

1	2	3
4	5	6
4	9	0

 

최대

행을 내려갈 때 마다 이전 행에 선택 가능 범위 내에 최대값을 구해서 합한 결과를 구함

1	2	3
6	8	9
14	18	9

 

최소

행을 내려갈 때 마다 이전 행에 선택 범위 내에 최소값을 구해서 합한 결과를 구함

1	2	3
5	6	8
9	14	6

 

참고

https://www.youtube.com/watch?v=uH9VJRIpIDY 

https://steady-coding.tistory.com/154

[BOJ] 백준 2096번 : 내려가기 (JAVA)

---

제출 코드

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();
    static InputProcessor inputProcessor = new InputProcessor();

    static int N, MAX_VALUE, MIN_VALUE;
    static int[][] DATA;
    static int[][] MAX_DP, MIN_DP;

    public static void main(String[] args) throws IOException {
        input();

        pro();

        output();
    }

    private static void input() {
        N = inputProcessor.nextInt();
        DATA = new int[N + 1][3];

        for(int i = 1; i <= N; i++) {
            for(int j = 0; j < 3; j++) {
                DATA[i][j] = inputProcessor.nextInt();
            }
        }

        // 초기화
        MAX_DP = new int[N + 1][3];
        MAX_DP[1][0] = DATA[1][0];
        MAX_DP[1][1] = DATA[1][1];
        MAX_DP[1][2] = DATA[1][2];

        MIN_DP = new int[N + 1][3];
        MIN_DP[1][0] = DATA[1][0];
        MIN_DP[1][1] = DATA[1][1];
        MIN_DP[1][2] = DATA[1][2];

        MAX_VALUE = 0;
        MIN_VALUE = Integer.MAX_VALUE;
    }

    private static void pro() {
        bottomUp();
    }

    private static void bottomUp() {
        for (int i = 2; i <= N; i++) {
            // 최대값
            MAX_DP[i][0] = Math.max(MAX_DP[i - 1][0], MAX_DP[i - 1][1]) + DATA[i][0];
            MAX_DP[i][1] = Math.max(MAX_DP[i - 1][0], Math.max(MAX_DP[i - 1][1], MAX_DP[i - 1][2])) + DATA[i][1];
            MAX_DP[i][2] = Math.max(MAX_DP[i - 1][1], MAX_DP[i - 1][2]) + DATA[i][2];

            //최소값
            MIN_DP[i][0] = Math.min(MIN_DP[i - 1][0], MIN_DP[i - 1][1]) + DATA[i][0];
            MIN_DP[i][1] = Math.min(MIN_DP[i - 1][0], Math.min(MIN_DP[i - 1][1], MIN_DP[i - 1][2])) + DATA[i][1];
            MIN_DP[i][2] = Math.min(MIN_DP[i - 1][1], MIN_DP[i - 1][2]) + DATA[i][2];
        }

        for (int i = 0; i <= 2; i++) {
            MIN_VALUE = Math.min(MIN_VALUE, MIN_DP[N][i]);
            MAX_VALUE = Math.max(MAX_VALUE, MAX_DP[N][i]);
        }

        sb.append(MAX_VALUE).append(" ").append(MIN_VALUE);
    }

    private static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static class InputProcessor {
        BufferedReader br;
        StringTokenizer st;

        public InputProcessor() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return st.nextToken();
        }

        public String nextLine() {
            String input = "";
            try {
                input = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }

            return input;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
    
}