백준 9465 풀이

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

스티커

문제의 조건은 다음과 같다.

1. 떼어낸 스티커의 상하좌우의 스티커를 이어서 뗄 수 없다.
2. 떼어낸 스티커의 점수의 총합이 최대가 되어야 한다.

떼어낸 스티커의 상하좌우를 연달아 뗄 수 없다면 일반적으로 한칸씩 건너 떼는 것을 생가할 것이다.

그런데 문제에 주어진 스티커의 배열은 2차원이기 때문에 대각선도 고려할 수 있다.

문제의 예시에서 50을 떼어냈다고 하면 다음으로 떼어낼 곳은 한칸 앞 대각선인 50과 두칸 앞 대각선인 70일 것이다.
물론 두칸 옆인 100도 가능은 하다. 하지만 점수를 최대로 얻을려면 대각선으로 내려가 2차원 형태를 최대한 활용해야한다.

아무튼 50을 처음에 떼어냈다면 다음 스티커를 떼어냄으로 얻을 수 있는 점수느 50+50 또는 50+70이 될 것이다. (1,1)의 값은 100이 되고 (1,2)의 값은 120이 된다.

그렇다면 (1,i)의 값은 어떻게 될까?

(1,2)의 값 120 같은 경우 어떻게 볼 수 있냐면, 한칸 뒤 대각선 점수 + 자신의 점수 또는 두칸 뒤 대각선 점수 + 자신의 점수가 될 수 있다.
둘 중 큰 값을 선택하겠지만...

즉, 점화식이

dp[1][i] = Max(dp[0][i-1], dp[0][i-2])

가 된다.
dp[0][i]도 마찬가지로 위치만 바꿔주면 된다.

끝!!

import java.io.*;

public class Main {
    /*static int count = -1;
    static int[] dx = {-2, -2, -1, -1, 1, 1, 2, 2};
    static int[] dy = {1, -1, 2, -2, 2, -2, 1, -1};*/
    //static boolean visited[];
    static int n, s;
    static int nums[];
    static int count = 0;
    static int mask[];

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            String num = br.readLine();
            n = Integer.parseInt(num);
            // n+1로 선언한 이유는 배열 탐색 과정에서 i-2에서 인덱스 범위 초과 문제를 막기 위해서
            int[][] arr = new int[2][n + 1];
            int[][] dp = new int[2][n + 1];

            for (int k = 0; k < 2; k++) {
                String[] tmp = br.readLine().split(" ");
                for (int l = 0; l < tmp.length; l++) {
                    arr[k][l + 1] = Integer.parseInt(tmp[l]);
                }
            }

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

            int ans = Math.max(dp[0][n], dp[1][n]);

            bw.write(ans+"\n");
        }

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