[백준] 9465번 : 스티커 - JAVA [자바]

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

---

변을 공유하는 스티커는 사용할 수 없다.

왼쪽부터 스티커를 뗀다고 생각해보자

제일 왼쪽 칸에 스티커의 위치를 위를 0 아래를 1 로 생각하자

첫번째 칸에서 0(위칸) 자리에 있는 스티커를 뗐으면
두번째 칸에서는 1(아래칸) 자리에 있는 스티커를 뗄 수 있다.

즉 전의 스티커를 뗀 위치에 따라 다음 스티커를 정해야 한다.

여기서 중요한 점이 스티커를 아에 안뗏다면
다음 스티커는 아무 스티커를 떼도 된다.

즉 안뗀다 0, 위칸 뗀다 1, 아래칸 뗀다 2로 배열을 정해서 풀어보자

0: 스티커를 안뗏을때
1: 윗칸 스티커를 뗏을때
2: 아래칸 스티커를 뗏을때

첫번째 칸은 그 전 칸이 없기 때문에 그 칸 자체의 cost 값이 그 칸에 스티커를 놓는 cost의 누적합이다.

dp[0][0] = 0;
dp[0][1] = cost[0][0];
dp[0][2] = cost[1][0];

다음 칸 부터는 3가지 경우(0,1,2)에 따라서 가능한 전 칸의 스티커 배치의 누적합 중 큰 것을 고르면 된다.

dp[n][0] : n 번째 칸에 스티커를 떼지 않는 경우
dp[n][1] : n 번째 칸에서 위칸에 스티커를 떼는 경우
dp[n][2] : n 번째 칸에서 아래칸에 스티커를 떼는 경우

이때 스티커를 떼지 않는 경우는(0) 전 칸에 세가지 경우가 전부 올 수 있으며 스티커를 떼지 않기 때문에 cost는 합에서 제외된다.

dp[n][0] = Math.max(dp[n-1][0], dp[n-1][1], dp[n-1][2]);
dp[n][1] = Math.max(dp[n-1][0], dp[n-1][2]) + cost[0][n-1];
dp[n][2] = Math.max(dp[n-1][0], dp[n-1][1]) + cost[1][n-1];

---

public class bj9465 {

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 변을 공유하는 스티커는 사용할 수 없다.
        // 왼쪽부터 스티커를 뗀다고 생각하자
        // 제일 왼쪽 칸에 스티커의 위치를 위를 0 아래를 1 로 생각하자
        // 첫번째 칸에서 0 자리에 있는 스티커를 뗐으면
        // 두번째 칸에서는 1 자리에 있는 스티커를 뗄 수 있다.
        // 즉 전의 스티커를 뗀 위치에 따라 다음 스티커를 정해야 한다.
        // 여기서 중요한 점이 스티커를 아에 안뗏다면
        // 다음 스티커는 아무 스티커를 떼도 된다.
        // 즉 안뗀다 0, 위칸 뗀다 1, 아래칸 뗀다 2로 배열을 정해서 풀어보자

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

        for (int t = 0; t < T; t++) {
            int N = Integer.parseInt(br.readLine());
            // cost 배열은 2 * N 크기 이다.
            // 메모리 초과 조심!!
            int[][] cost = new int[2][N];
            
            // cost 배열 저장
            String[] split = br.readLine().split(" ");
            for (int i = 0; i < N; i++) {
                cost[0][i] = Integer.parseInt(split[i]);
            }
            split = br.readLine().split(" ");
            for (int i = 0; i < N; i++) {
                cost[1][i] = Integer.parseInt(split[i]);
            }

			// 세가지 경우의 누적합을 구하기 위해 long[N][3]
            long[][] dp = new long[N][3];

            // 저장한 cost 값을 통해
            // 첫번째 칸부터
            // 0: 스티커를 안뗏을때
            // 1: 윗칸 스티커를 뗏을때
            // 2: 아래칸 스티커를 뗏을때
            // 다음 칸에서 스티커를 떼는 누적합을 구하면 된다.

            // 일단 제일 처음 칸의 누적합은 그 cost 자체이기 때문에 초기화
            dp[0][0] = 0;
            dp[0][1] = cost[0][0];
            dp[0][2] = cost[1][0];

            // dp[n][0] = Math.max(dp[n-1][0], dp[n-1][1], dp[n-1][2]);
            // dp[n][1] = Math.max(dp[n-1][0], dp[n-1][2]) + cost[0][n-1];
            // dp[n][2] = Math.max(dp[n-1][0], dp[n-1][1]) + cost[1][n-1];
            for (int i = 1; i < N; i++) {
                dp[i][0] = Math.max(Math.max(dp[i - 1][0], dp[i - 1][1]), dp[i - 1][2]);
                dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][2]) + cost[0][i];
                dp[i][2] = Math.max(dp[i - 1][0], dp[i - 1][1]) + cost[1][i];
            }

            long answer = Math.max(Math.max(dp[N - 1][0], dp[N - 1][1]), dp[N - 1][2]);
            bw.write(answer + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

MOD 나누기가 없으므로 잘 확인하자..