[BOJ 2156] 포도주 시식(Java, DP)

 

---

문제 링크 

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

2156번: 포도주 시식

---

문제 풀이 

- 시간복잡도 O(N)

- 초기항 구하고, N번째 포도주에 대해 아래 3가지 경우를 비교하여 최대 값 구함 

 

이때 3번 연달아 포도주를 마실 수 없다는 규칙에 따라 DP 테이블을 갱신한다

 

i번째 포도주를 마시지 않는 경우

① DP[i - 1]할당

 

i번째 포도주를 마시는 경우

② i - 1 번째 포도주 먹고 마시는 경우 최대치 (DATA[i - 1] + DP[i - 3])

③ i - 2 번째 포도주 먹고 마시는 경우 최대치 (DP[i - 2])

 

결국 DP[N] 에는 i번째 포도주를 마시는 경우와 마시지 않는 경우 중 최대값이 들어있게 된다

 

 

초기항 

DP[0] = 0;

DP[1] = DATA[1];

DP[2] = DATA[1] + DATA[2]; ( N >= 2 이상인 경우 )

---

제출 코드 

(1) Bottom-Up 방식

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

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

    private static int N;
    private static int[] DP, DATA;

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

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

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

    private static void pro() {
        DP[1] = DATA[1];

        if (N >= 2) {
            DP[2] = DATA[1] + DATA[2];
        }

        for (int i = 3; i <= N; i++) {
            DP[i] = DP[i - 1];
            int drunk = Math.max(DATA[i - 1] + DP[i - 3], DP[i - 2]) + DATA[i];
            DP[i] = Math.max(DP[i], drunk);
        }

        sb.append(DP[N]);
    }

    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());
        }

    }
}

 

(2) Top-Down 방식

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

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

    private static int N;
    private static int[] DP, DATA;

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

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

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


    private static void pro() {
        // 초기화
        Arrays.fill(DP, -1);
        DP[1] = DATA[1];
        if (N >= 2) {
            DP[2] = DATA[1] + DATA[2];
        }

        sb.append(topDown(N));
    }

    private static int topDown(int node) {
        if (node < 1) return 0;
        if (DP[node] != -1) return DP[node];

        DP[node] = topDown(node - 1);

        int drunk = Math.max(DATA[node - 1] + topDown(node - 3), topDown(node - 2)) + DATA[node];

        return DP[node] = Math.max(DP[node], drunk);
    }


    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());
        }

    }
    
}