[Java] 9465. 스티커

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

문제 접근 과정

• 선택 가능한 경우의 수
  • 양옆 불가: 같은 열의 다른 행에 위치한 스티커를 선택할 수 없습니다.
  • 위아래 불가: 인접한 대각선 방향의 스티커도 선택할 수 없습니다.
  • 대각선 가능: 한 칸 떨어진 대각선 또는 두 칸 떨어진 대각선의 스티커는 선택 가능합니다.

• 한 칸 떨어진 대각선: 현재 스티커와 같은 열의 반대편 스티커에서 이어지는 경우.
• 두 칸 떨어진 대각선: 현재 스티커와 같은 열보다 2칸 앞에 있는 반대편 스티커에서 이어지는 경우.

한 칸 대각선과 두 칸 대각선을 포함한 세 칸 이상의 대각선은 이미 점화식에서 표현 가능합니다.

 

점화식

DP 배열 정의

• dp[0][j]: 첫 번째 행의 j번째 열 스티커를 선택했을 때 얻을 수 있는 최대 점수.
• dp[1][j]: 두 번째 행의 j번째 열 스티커를 선택했을 때 얻을 수 있는 최대 점수.

점화식:

dp[0][j]= map[0][j] + max⁡(dp[1][j−1], dp[1][j−2])

dp[1][j]= map[1][j] + max⁡(dp[0][j−1], dp[0][j−2])

• map[0][j]: 첫 번째 행의 j번째 열 스티커 점수.
• map[1][j] 두 번째 행의 j번째 열 스티커 점수.
• max(dp[k][j−1], dp[k][j−2]): 바로 이전 열과 두 칸 이전 열의 최대 점수.

초기조건:

j=0: 첫 번째 열은 이전 열이 없으므로 스티커 자체 점수가 최대 점수.

• dp[0][0]=map[0][0]
• dp[1][0]=map[1][0]

j=1: 두 번째 열은 한 칸 떨어진 대각선만 고려. (전전 열이 없기때문에)

• dp[0][1]=map[0][1]+dp[1][0]
• dp[1][1]=map[1][1]+dp[0][0]

 

코드

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

public class Main {
    private static int[][] dp;
    private static int[][] map;

    private static int cal(int row, int col) {
        if (col < 0) return 0;

        if (dp[row][col] != -1) {
            return dp[row][col];
        }

        int oppositeRow = 1 - row;
        dp[row][col] = map[row][col] + Math.max(cal(oppositeRow, col - 1), cal(oppositeRow, col - 2));
        return dp[row][col];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testcase = Integer.parseInt(br.readLine());

        StringBuilder result = new StringBuilder();

        for (int t = 0; t < testcase; t++) {
            int n = Integer.parseInt(br.readLine());
            dp = new int[2][n];
            map = new int[2][n];

            for (int[] row : dp) {
                Arrays.fill(row, -1);
            }

            for (int i = 0; i < 2; i++) {
                String[] input = br.readLine().split(" ");
                for (int j = 0; j < n; j++) {
                    map[i][j] = Integer.parseInt(input[j]);
                }
            }

            int maxScore = Math.max(cal(0, n - 1), cal(1, n - 1));
            result.append(maxScore).append("\n");
        }

        System.out.print(result.toString());
    }
}