[백준 / 실버1] 9465 스티커 (Java)

문제 보기

사용한 것

• 현재 스티커를 최대의 점수로 떼기 위한 bottom-up

풀이 방법

• 현재 스티커를 최대의 점수로 뗄 수 있는 후보는 다음과 같다.
  • 컬럼 2만큼 전에서 같은 row의 스티커를 뗀 경우
  • 컬럼 2만큼 전에서 다른 row의 스티커를 뗀 경우
  • 컬럼 1만큼 전에서 다른 row의 스티커를 뗀 경우
• 따라서 위 3가지 경우의 최대 값에서 현재 스티커를 더해서 dp배열에 저장한다.

코드

public class Main {

    public static void main(String[] args) throws IOException {
        // 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            int[][] stickers = new int[n + 2][2];
            st = new StringTokenizer(br.readLine());
            for (int j = 2; j < n + 2; j++) {
                stickers[j][0] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            for (int j = 2; j < n + 2; j++) {
                stickers[j][1] = Integer.parseInt(st.nextToken());
            }

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

            int maxScore = 0;
            for (int j = 2; j < n + 2; j++) {
                maxScore = Math.max(dp[j][0], maxScore);
                maxScore = Math.max(dp[j][1], maxScore);
            }
            sb.append(maxScore).append(lineSeparator());
        }

        System.out.println(sb);
    }
}