[백준] 9465번 - 스티커 [Java]

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

 

[백준] 9465번 - 스티커 [Java]

[백준] 9465번 - 스티커 [Java]

---

1.  아이디어

 

다이나믹 프로그래밍을 활용하면 최댓값을 구할 수 있다.

---

2. 문제풀이

 

스티커를 떼면 상하좌우에 있는 스티커는 떼어낼 수 없다. 이를 활용해서 2차원 배열 map에 스티커의 점수를 저장하고 같은 크기의 dp 배열을 만들었다. dp 배열은 해당 위치의 스티커를 뗐을 때 점수의 최댓값을 저장하는데 해당 위치의 스티커를 뗐을 때 최댓값은 왼쪽 대각선에 있는 스티커까지 뗀 경우와 왼쪽 대각선보다 한칸 왼쪽에 있는 스티커를 뗀 경우 두가지 중 최댓값과 비교하는 방식으로 동작한다. 바로 왼쪽 스티커를 뗀 경우에는 현재 위치의 스티커를 뗄 수 없고 왼쪽으로 2칸 위치의 스티커를 뗀 경우에는 왼쪽 대각선 스티커를 떼도 되기 때문에 2가지 경우만 비교해보면 된다.

---

3. 코드

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            int N = Integer.parseInt(br.readLine());

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

            int[][] dp = new int[2][2 + N];
            for (int j = 2; j < N + 2; j++) {
                dp[0][j] = Math.max(dp[1][j - 1], dp[1][j - 2]) + map[0][j];
                dp[1][j] = Math.max(dp[0][j - 1], dp[0][j - 2]) + map[1][j];
            }

            sb.append(Math.max(dp[0][N + 1], dp[1][N + 1])).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }
}

---

4. 후기