[백준/9465] 스티커 - JAVA

📌 문제

알고리즘 분류 : DP
난이도 : 실버1
출처 : 백준 - 스티커

🦧 문제 풀이 접근

바로 인접한 스티커는 고를 수 없기 때문에 다른행에 1칸전과 2칸전에 값을 비교하여 dp를 해결한다.

💻 code

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));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        while(T-->0) {
            int n = Integer.parseInt(br.readLine());
            int[][] point = 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++) {
                    point[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            dp[0][1] = point[0][1];
            dp[1][1] = point[1][1];
            int max = Math.max(dp[0][1],dp[1][1]);
            for(int i=2;i<=n;i++) {
                dp[0][i] = Math.max(dp[1][i-1],dp[1][i-2])+point[0][i];
                dp[1][i] = Math.max(dp[0][i-1],dp[0][i-2])+point[1][i];
                max = Math.max(max,Math.max(dp[0][i],dp[1][i]));
            }
            sb.append(max).append("\n");
        }
        System.out.println(sb);
    }
}

🥇 결과

🎓 느낀점

2차원 배열 dp 문제지만 2개만 비교하면 되기 때문에 크게 두 스티커관의 관계만 이해한다면 쉽게 풀 수 있다.