[BOJ] 2096.내려가기(DP, 슬라이드 윈도우).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

문제에서 주어진 제약조건대로 구현(?)한다는 느낌으로 하면 될 것 같다.

참고로 메모리 제한이 있다..!

최대 N은 100,000 으로 나이브하게 짜면

- 숫자 정보 배열 100,000 x 100,000

- min dp 배열 100,000 x 100,000

- max dp 배열 100,000 x 100,000

가 필요하게 된다.

그렇기 때문에 

2 x 100,000 배열을 사용해서 결과를 밀어가면서 해결하는

슬라이드 윈도우 방법도 적용해야 한다.

#. Code

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

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer;   public class BOJ2096 {       public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;                  int N = Integer.parseInt(br.readLine());         int[][] min = new int[2][3];         int[][] max = new int[2][3];           int a, b, c;         for (int i = 0; i < N; i++) {                          st = new StringTokenizer(br.readLine());             a = Integer.parseInt(st.nextToken());             b = Integer.parseInt(st.nextToken());             c = Integer.parseInt(st.nextToken());                          // 최소 구하기             min[1][0] = a + Math.min(min[0][0], min[0][1]);             min[1][1] = b + Math.min(min[0][0], Math.min(min[0][1], min[0][2]));             min[1][2] = c + Math.min(min[0][1], min[0][2]);             System.arraycopy(min[1], 0, min[0], 0, 3);                          max[1][0] = a + Math.max(max[0][0], max[0][1]);             max[1][1] = b + Math.max(max[0][0], Math.max(max[0][1], max[0][2]));             max[1][2] = c + Math.max(max[0][1], max[0][2]);             System.arraycopy(max[1], 0, max[0], 0, 3);         }                  Arrays.sort(min[1]);         Arrays.sort(max[1]);                  System.out.println(max[1][2] + " " + min[1][0]);     } } Colored by Color Scripter

cs

#. Other_v2

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 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer;   public class BOJ2096 {       public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;                  int N = Integer.parseInt(br.readLine());         int[] min = new int[3];         int[] max = new int[3];           // 첫 줄 세팅         st = new StringTokenizer(br.readLine());         for (int i = 0; i < 3; i++) {             int tmp = Integer.parseInt(st.nextToken());                          min[i] = tmp;             max[i] = tmp;         }                  int a, b, c, n0, n1, n2;         for (int i = 0; i < N - 1; i++) {                          st = new StringTokenizer(br.readLine());             a = Integer.parseInt(st.nextToken());             b = Integer.parseInt(st.nextToken());             c = Integer.parseInt(st.nextToken());                          // 최소 구하기             n0 = n1 = n2 = 0;             n0 = min[0] + a;             n1 = min[0] + b;                          n0 = Math.min(n0, min[1] + a);             n1 = Math.min(n1, min[1] + b);             n2 = min[1] + c;                          n1 = Math.min(n1, min[2] + b);             n2 = Math.min(n2, min[2] + c);                          min[0] = n0;             min[1] = n1;             min[2] = n2;                          // 최대 구하기             n0 = n1 = n2 = 0;             n0 = max[0] + a;             n1 = max[0] + b;                          n0 = Math.max(n0, max[1] + a);             n1 = Math.max(n1, max[1] + b);             n2 = max[1] + c;                          n1 = Math.max(n1, max[2] + b);             n2 = Math.max(n2, max[2] + c);                          max[0] = n0;             max[1] = n1;             max[2] = n2;         }                  Arrays.sort(min);         Arrays.sort(max);                  System.out.println(max[2] + " " + min[0]);     }   }   Colored by Color Scripter

cs