백준 Java 9465_스티커

왼쪽 대각선 아래, 왼쪽 대각선 아래의 왼쪽만 확인해서 더 큰 값을 현재 위치에 넣어주면 된다! 4번 경우를 DP로 생각한다면, 이미 dp[1][2]에 (0,1)과 (1,2)의 합이 들어있기 때문에 dp[1][2]와 dp[1][1] 중에 큰 값과 (0,3)값을 더해 dp[0][3]에 저장하면 된다

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

public class Main {
    

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

        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            int[][] sticker = new int[2][N + 1];
            int[][] dp = new int[2][N + 1];

            for (int i = 0; i < 2; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 1; j <= N; j++) {
                    sticker[i][j] = Integer.parseInt(st.nextToken());
                }
            }
// 첫번째 column은 자기 자신이 최대이므로 자기 자신으로 초기화
                dp[0][1] = sticker[0][1];
                dp[1][1] = sticker[1][1];

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

                }
                int max = Math.max(dp[0][N], dp[1][N]);
                sb.append(max).append("\n");
            }
System.out.print(sb);
        }
        }

참조 : https://velog.io/@yanghl98/백준-9465-스티커-JAVA