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

 

2096번: 내려가기

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

www.acmicpc.net

기본적인 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을 반복적으로 참조하는 식으로 하였습니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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();
    }
}
cs

'algorithm > dp' 카테고리의 다른 글

boj 17528 Two Machines  (0) 2021.01.28
boj 9657 돌 게임 3  (0) 2021.01.27
boj 1103 게임  (0) 2021.01.22
boj 12852 1로 만들기 2  (0) 2021.01.22
boj 16195 1, 2, 3 더하기 9  (0) 2021.01.22

+ Recent posts

티스토리툴바