[백준, Java] 9465번 : 스티커

🔗 문제 링크

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

😮 문제 해결 방법

매 열마다 1행 혹은 2행의 스티커를 뜯었을 때의 최대 점수를 구해주면 되기 때문에 2차원 배열로 선언해준다.

최대 점수는 n열까지 모두 뜯었을 때 1행 n열 혹은 2행 n열의 점수 중 큰 점수가 가장 최대로 구할 수 있는 점수이다.

 

현재 열이 3열이라고 가정하고 스티커를 뜯는 경우를 판단해보자.

3열의 스티커를 뜯는 경우는 1행 3열, 2행 3열의 스티커를 뜯는 경우 2가지이다.

1행 3열의 스티커를 뜯는 경우 → row : 0 col : 2

 

• 인접한 변을 가진 스티커는 뜯을 수 없기 때문에 **이전 열 대각선(현재 행과 반대되는 행)**에 위치한 최대 점수 값과 현재 스티커 점수를 더해준다. → dp[prevRow][col - 1] + sticker[row][col]
  • row가 0이므로 대각선의 row는 1일 것이고, 이전 열이기 때문에 이전 열은 col -1이다.

 

• 한 칸 띄워진 경우는 1행 2행 모두 현재 스티커와 인접하지 않기 때문에 둘 중하나를 뜯어줄 수 있다.
  • 한 칸 띄워진 1행을 뜯는 경우 : dp[0][col-2] + sticker[row][col]
  • 한 칸 띄워진 2행을 뜯는 경우 : dp[1][col-2] + sticker[row][col]

2행 3열의 스티커를 뜯는 경우도 1행 3열의 스티커를 뜯는 것과 이전 열에 대한 행만 반대로 판단해주면 된다.

 

이렇게 최대로 구할 수 있는 방법을 하나의 점화식으로 나타내보면 아래와 같다.

dp[row][col] = Math.max(sticker[row][col] + dp[prevRow][col - 1], Math.max(sticker[row][col] + dp[0][col - 2], sticker[row][col] + dp[1][col - 2]))

 

모든 열에 대해 최대 점수를 구하고, 마지막 열의 두 행 중 최대 점수를 리턴해준다.

🚩 Java 코드

package com.algorithm.Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_9465_스티커 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        for (int loop = 0; loop < T; loop++) {
            int N = Integer.parseInt(br.readLine());
            int[][] sticker = new int[2][N];

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

            int rst = getMaxScore(N, sticker);
            System.out.println(rst);
        }

        br.close();
    }

    private static int getMaxScore(int n, int[][] sticker) {
        if (n == 1) return Math.max(sticker[0][0], sticker[1][0]);
        if (n == 2) return Math.max(sticker[0][0] + sticker[1][1], sticker[0][1] + sticker[1][0]);

        // 각 열마다 획득할 수 있는 최대 점수
        int[][] dp = new int[2][n];
        dp[0][0] = sticker[0][0];
        dp[1][0] = sticker[1][0];
        dp[0][1] = dp[1][0] + sticker[0][1];
        dp[1][1] = dp[0][0] + sticker[1][1];

        /**
         * row : 현재 행, col : 현재 열
         * 1. sticker[row][col]을 뜯는 경우 기준
         * 2. dp[0][col-2], dp[1][col-2] 처럼 한 칸 띄워진 경우이므로 두 행의 점수 중 큰 값을 가져와 더해줄 수 있다.
         * 3. dp[prevRow][col - 1] 현재 스티커 기준 이전 열의 대각선에 위치한 점수만 가져올 수 있다.
         * 점화식 : dp[row][col] = Math.max(sticker[row][col] + dp[prevRow][col - 1], Math.max(sticker[row][col] + dp[0][col - 2], sticker[row][col] + dp[1][col - 2]))
         */

        // 매 열마다 최대로 얻을 수 있는 점수 구하기
        for (int col = 2; col < n; col++) {
            for (int row = 0; row < 2; row++) {
                int prevRow = row == 1 ? 0 : 1;
                dp[row][col] = Math.max(sticker[row][col] + dp[prevRow][col - 1], Math.max(sticker[row][col] + dp[0][col - 2], sticker[row][col] + dp[1][col - 2]));
            }
        }

        return Math.max(dp[0][n - 1], dp[1][n - 1]);
    }
}