P.9465 스티커

코드

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

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

        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());

            int[][] stickers = new int[2][n];
            for (int i = 0; i < 2; i++) stickers[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            int result = Math.max(stickers[0][0], stickers[1][0]);
            int[][] dp = new int[n][3];
            dp[0][0] = stickers[0][0]; dp[0][1] = stickers[1][0]; dp[0][2] = 0;
            for (int i = 1; i < n; i++) {
                dp[i][0] = stickers[0][i] + Math.max(dp[i - 1][1], dp[i - 1][2]);
                dp[i][1] = stickers[1][i] + Math.max(dp[i - 1][0], dp[i - 1][2]);
                dp[i][2] = Math.max(dp[i - 1][0], dp[i - 1][1]);

                result = Math.max(dp[i][0], dp[i][1]);
                result = Math.max(result, dp[i][2]);
            }

            bw.write(result + "\n");
        }
        bw.flush();
    }
}

코드 설명

메모리 초과 때문에 꽤나 애를 먹었던 문제다.

처음엔 그리디인 줄 알았는데, 그리디로 풀기에는 시간이 부족했다.

이전 스티커 중 어떤 것을 제거했는지가 이번 스티커에 영향을 미치기 때문에 dp로 풀었다.

 

dp[n][0]은 [0][n] 스티커를 선택했을 때 받을 수 있는 점수의 최댓값이라는 점에서 착안을 했다.

dp[n][1]은 [1][n] 스티커를 선택했을 때이고, dp[n][2]는 n번째 행에서 아무것도 선택하지 않았을 때 최댓값을 의미한다.

 

dp[n][0]스티커를 선택하기 위해서는 [0][n - 1]번째 스티커를 선택해서는 안된다. 

전 행에서 아무것도 선택하지 않았거나, 1열의 스티커를 선택했어야 한다.

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

 

dp[n][1] 스티커를 선택하기 위해서는 [1][n - 1]번째 스티커를 선택해서는 안된다.

전 행에서 아무것도 선택하지 않았거나, 0열의 스티커를 선택했어야 한다.

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

 

dp[n][2]는 스티커를 선택하지 않을 때이다.

이 때는 전 행에서의 최댓값을 갖게 된다.

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

 

또, result를 0으로 초기화를 하면 n이 1일 때 답으로 무조건 0이 나오게 된다.

이 부분은 0행의 스티커들의 최댓값으로 초기화를 해 주면 해결된다.

 

식이 쉬운 거에 비해서 메모리초과로 꽤 헤맸는데 이건 stickers를 받을 때 배열을 [n][n]으로 초기화를 해 주어서였다.

[2][n]으로 딱 맞게 초기화를 하면 맞았습니다!!가 뜬다.