[9465번] 스티커

문제링크 : https://www.acmicpc.net/problem/9465

 

1. 문제 이해

• 2행 N열로 스티커가 주어진다.
• 스티커를 뜯으면 점수를 얻는다.
• 한 번에 인접한 스티커는 뜯을 수 없다.
  • 인접이란? 위/아래/왼쪽/오른쪽.
• 목표: 얻을 수 있는 최대 점수를 구하라.

 

브루트포스? → ❌ 

가능한 조합을 전부 탐색?

N ≤ 100,000이므로 지수 시간복잡도는 시간 초과 따라서 부분 문제로 쪼개서 푸는 동적 계획법 (DP) 사용해야 한다.

 

2. DP 상태 정의

각 열에서 "이번에 윗줄/아랫줄 중 어떤 걸 뜯느냐"에 따라 점수가 달라진다.

그래서 다음과 같이 정의했다.

 

dp[i][0] = i번째 열에서 윗줄 스티커를 선택했을 때의 최대 점수
dp[i][1] = i번째 열에서 아랫줄 스티커를 선택했을 때의 최대 점수

 

3. 점화식 설계

i번째 열에서 윗줄을 선택했다면,
→ 아랫줄의 i-1 또는 i-2를 선택했을 수 있음 (인접 피하기 위해)

dp[i][0] = max(dp[i-1][1], dp[i-2][1]) + sticker[0][i]

 

반대로 아랫줄을 선택했다면,
→ 윗줄의 i-1 또는 i-2를 선택했을 수 있음

 

dp[i][1] = max(dp[i-1][0], dp[i-2][0]) + sticker[1][i]

 

 

4. 초기값 설정

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

 

6. 정답 

 

import java.util.Scanner;

public class _9465 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int T  = sc.nextInt(); // 테스트 케이스 개수

        for (int i = 0; i < T; i++) {

            int n = sc.nextInt();

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

            // 스티커 입력
            for (int j = 0; j < 2; j++) {
                for (int k = 1; k <= n; k++) {
                    arr[j][k] = sc.nextInt();
                }
            }

            // 초기값 설정
            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 - 1], dp[1][j - 2]) + arr[0][j];
                dp[1][j] = Math.max(dp[0][j - 1], dp[0][j - 2]) + arr[1][j];
            }

            // 최댓값 출력
            System.out.println(Math.max(dp[0][n], dp[1][n]));
        }

        sc.close();
    }
}