백준 14501번 - 스티커

문제

백준 14501번 - 스티커

아이디어

• 첫 스티커를 위와 아래 중 어디부터 시작하느냐에 따라 최댓값에 영향을 줄 수 있으므로 DP를 사용해 해결한다.
• dp[n][0 or 1]을 0(위) 또는 1(아래) 스티커부터 시작했을 때 n번째 열의 최댓값이라고 가정한다.
• 문제 조건으로 대각선 이동만 할 수 있으므로 현재 위치를 고를 수 있는 이전 위치는 이전(왼쪽) 대각선 한 칸 전, 두 칸 전이 되므로 다음과 같이 dp 배열을 채울 수 있다.

dp[n][0] = max(dp[n-1][1], dp[n-2][1]) + 현재 스티커
dp[n][1] = max(dp[n-1][0], dp[n-2][0]) + 현재 스티커

• 마지막에 dp[n][0]과 dp[n][1] 중 큰 값이 정답이 된다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N)

코드 구현

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

public class BJ_14501 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int t = Integer.parseInt(br.readLine());

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

            int[][] arr = new int[n + 1][2];
            int[][] dp = new int[n + 1][2];

            for (int i = 0; i < 2; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 1; j <= n; j++) {
                    arr[j][i] = Integer.parseInt(st.nextToken());
                }
            }

            dp[1][0] = arr[1][0];
            dp[1][1] = arr[1][1];

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

            sb.append(Math.max(dp[n][0], dp[n][1])).append("\n");
        }

        System.out.print(sb);
    }
}