boj 2096 내려가기

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

2096번: 내려가기

기본적인 dp로 해결가능한 문제입니다.

 

각 칸의 최대/최소는

dp(i,0)의 값은 dp(i-1, 0), dp(i-1, 1)의 최대/최소

dp(i,1)의 값은 dp(i-1, 0), dp(i-1, 1), dp(i-1, 2)의 최대/최소

dp(i,2)의 값은 dp(i-1, 1), dp(i-1, 2)의 최대/최소

에서 해당 칸의 값을 더한 값으로 계산할 수 있습니다.

 

하지만 이 문제는 C++로 해결할 경우에 메모리제한이 4MB, JAVA로 해결할 경우에 256MB이 걸려있습니다.

 

메모리 절약을 위해 슬라이딩 윈도우 기법을 이용하였습니다.

이 문제는 i번째 줄의 값들을 구하기 위해서는 i-1번째 줄의 값만 있으면 됩니다.

따라서 공간은 2*3의 크기만큼 있으면 되고, 인덱스는 0과 1을 반복적으로 참조하는 식으로 하였습니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int maxdp[][], mindp[][];
    static int N, t;
 
    static void print() {
        t = 1 - t;
        int maxans = Math.max(maxdp[t][0], Math.max(maxdp[t][1], maxdp[t][2]));
        int minans = Math.min(mindp[t][0], Math.min(mindp[t][1], mindp[t][2]));
 
        System.out.println(maxans + " " + minans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        maxdp = new int[2][3];
        mindp = new int[2][3];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            maxdp[t][0] = Math.max(maxdp[1 - t][0], maxdp[1 - t][1]) + a;
            maxdp[t][1] = Math.max(maxdp[1 - t][0], Math.max(maxdp[1 - t][1], maxdp[1 - t][2])) + b;
            maxdp[t][2] = Math.max(maxdp[1 - t][1], maxdp[1 - t][2]) + c;
 
            mindp[t][0] = Math.min(mindp[1 - t][0], mindp[1 - t][1]) + a;
            mindp[t][1] = Math.min(mindp[1 - t][0], Math.min(mindp[1 - t][1], mindp[1 - t][2])) + b;
            mindp[t][2] = Math.min(mindp[1 - t][1], mindp[1 - t][2]) + c;
 
            
            t = 1 - t;
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        print();
    }
}