[BOJ 9465] 스티커 (Java, DP)

 

---

문제 링크

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

9465번: 스티커

---

문제 풀이 

- 시간 복잡도 O(N), 최대치 Integer 범위 내

- 스티커 하나를 뜯을 경우 상하좌우로 찢어져서 사용할 수 없게 됨 

- 2 x N열 스티커, 2차원 배열 형태의 DP 문제

 

초기화

	1
DP[0][i]	50
DP[1][i]	30

 

0번행의 2열 스티커를 뽑을 경우 아래 선택가능한 영역에서 최대치를 뽑아 더해주면 됨 

0	1	2
O		스티커 선택
O	O

 

1번행의 2열 스티커를 뽑을 경우 아래 선택가능한 영역에서 최대치를 뽑아 더해주면 됨

0	1	2
O	O
O		스티커 선택

 

N열까지 갱신하게 될 경우 DP[0][N], DP[1][N] 중 최대값을 구하면 정답 맞출 수 있다

---

제출 코드 

bottom-up방식

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

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

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

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        T = Integer.parseInt(br.readLine());
        while(T > 0) {
            T -= 1;

            N = Integer.parseInt(br.readLine());
            DATA = new int[2][N + 1];

            for(int i = 0; i < 2; i++) {
                st = new StringTokenizer(br.readLine());
                for(int j = 1; j <= N; j++) {
                    DATA[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            DP = new int[2][N + 1];
            pro();
        }
    }

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

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

        int result = Math.max(DP[0][N], DP[1][N]);
        sb.append(result).append("\n");
    }

    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sb);
    }
    
}

 

 

top-down 방식 

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

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

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

    public static void main(String[] args) throws IOException {
        T = inputProcessor.nextInt();
        while(T > 0) {
            input();
            pro();
            T -= 1;
        }

        output();
    }

    private static void input() {
        N = inputProcessor.nextInt();
        DATA = new int[3][N + 1];
        for(int i = 1; i <= 2; i++) {
            for(int j = 1; j <= N; j++) {
                DATA[i][j] = inputProcessor.nextInt();
            }
        }

        DP = new int[N + 1][2];
        for(int i = 1; i <= N; i++) Arrays.fill(DP[i], -1);

        DP[0][0] = 0;
        DP[0][1] = 0;
        DP[1][0] = DATA[1][1];
        DP[1][1] = DATA[2][1];
    }

    private static void pro() {
        sb.append(Math.max(topDown(N, 0), topDown(N , 1))).append("\n");
    }

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

        if(idx == 0) {
            // 앞에 스티커를 때거나, n - 2 스티커 중 선택하거나
            DP[n][0] = topDown(n - 1, 1) + DATA[1][n];
            DP[n][0] = Math.max(DP[n][0], Math.max(topDown(n - 2, 0), topDown(n - 2, 1)) + DATA[1][n]);
        } else if(idx == 1) {
            DP[n][1] = topDown(n - 1, 0) + DATA[2][n];
            DP[n][1] = Math.max(DP[n][1], Math.max(topDown(n - 2, 0), topDown(n - 2, 1)) + DATA[2][n]);
        }

        return DP[n][idx];
    }


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

    }
    
}