백준 9465번 (DP) - 스티커 (JAVA) 문제 풀이

https://www.acmicpc.net/problem/9465

9465번: 스티커

---

 

✏️ 문제

---

 

🔐 문제 해결

해당 문제는 2xN 스티커가 주어졌을 때, 스티커를 골라 가장 높은 점수의 합을 구하는 문제입니다. 이때 고른 스티커의 좌,우,상,하 스티커는 선택할 수 없게 됩니다.

원래 이 문제는 가로로 arr[0][0] -> arr[0][1] ... -> arr[1][N] 이런 식으로 진행하면서 계산하려 했더니 실패하여서

세로 (arr[0][1] -> arr[1][1] -> arr[2][0] ... -> arr[1][N])로 접근하는 방식으로 문제를 해결하였습니다.

먼저 스티커를 보겠습니다.

각 행과 열의 시작 인덱스를 0과 1이라고 한다면, 가장 큰 점수의 조합은 arr[0][1], arr[1][2], arr[0][3], arr[1][5] 이렇게 4개를 선택한 경우입니다. dp 배열을 하나 생성하여 사용했는지 않했는지를 체크해주면서 진행하면 될 것 같습니다.

 

1. 테이블 정의

dp[i][n][m] 는 i행 n열의 스티커를 선택했는지에 여부(m)에 따른 점수의 최대의 합이라고 정의하였습니다.

• i는 0, 1의 값을 가집니다.
• n은 1보다 크거나 같고, N보다 작거나 같습니다.
• m은 0, 1의 값을 가집니다.

 

2. 점화식 세우기

먼저 그림을 보고 값을 구하면서 점화식을 세워보도록 하겠습니다.

 

i가 2일 때의, 윗 변을 먼저 계산해보도록 하겠습니다.

• arr[0][2][0] = [0][2]의 스티커를 선택하지 않은 경우입니다. 아래 값들 중 최댓 값을 선택하면 됩니다.
  • [1][1] 스티커를 선택하지 않은 경우
  • [1][1] 스티커를 선택한 경우
  • (dp[1][1] 배열에 이전까지 점수들을 계산하였기 때문에 최댓 값을 넣어줍니다.)
• arr[0][2][1] = [0][2]의 스티커를 선택하는 경우입니다. 아래의 값들 중 최댓 값을 선택하여 + arr[0][2] 값이 됩니다.
  • [0][1] 스티커를 선택하지 않은 경우
  • [1][1] 스티커를 선택한 경우

 

그 다음 밑 변을 계산해보도록 하겠습니다.

• arr[1][2][0] = [1][2] 스티커를 선택하지 않은 경우입니다. 아래의 값들 중 최대 값을 선택하면 됩니다.
  • [1][1] 스티커를 선택한 경우와 선택하지 않은 경우 (즉, [0][2]를 선택하지 않은 경우의 값과 같다.)
  • [0][2] 스티커를 선택한 경우와 선택하지 않은 경우
• arr[1][2][1] = [1][2] 스티커를 선택한 경우입니다.
  • [1][1] 스티커를 선택하지 않은 경우와 arr[1][2] 값의 합이 됩니다.

 

점화식으로 나타내면 아래와 같습니다.

dp[0][i][0] = Math.max(dp[1][i-1][0], dp[1][i-1][1]);
dp[0][i][1] = Math.max(dp[0][i-1][0], dp[1][i-1][1]) + arr[0][i];

dp[1][i][0] = Math.max(dp[0][i][0], dp[0][i][1]);
dp[1][i][1] = dp[1][i-1][0] + arr[1][i];

 

3. 초기값 설정

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

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

• dp[0][1][0] = [0][1] 스티커를 선택하지 않았을 경우에는 당연히 합이 0일 것입니다.
• dp[0][1][1] = [0][1] 스티커를 선택한 경우에는 해당 스티커의 값을 가집니다.
• dp[1][1][0] = [1][1] 스티커를 선택하지 않았을 경우에는 이전 스티커를 선택한 값과 같을 것입니다.
• dp[1][1][1] = [1][1] 스티커를 선택한 경우에는 [0][1] 스티커를 선택할 수 없습니다. arr[0][1] 값만 갖습니다.

---

 

🗝 전체 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(bf.readLine());
        int N = 0;
        int[][] arr;
        int[][][] dp;

        for(int t=0; t<T; t++){
             N = Integer.parseInt(bf.readLine());

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


             for(int p=0; p<2; p++) {
                 st = new StringTokenizer(bf.readLine());

                 for(int i=1; i<=N; i++) {
                     arr[p][i] = Integer.parseInt(st.nextToken());
                 }
             }

            // 윗 변 초기값 설정
            dp[0][1][0] = 0;
            dp[0][1][1] = arr[0][1];
            // 밑 변 초기값 설정
            dp[1][1][0] = dp[0][1][1];
            dp[1][1][1] = dp[0][1][0] + arr[1][1];

            // dp 시작
            for(int n=2; n<=N; n++) {
                // 윗 변 계산
                dp[0][n][0] = Math.max(dp[1][n-1][0], dp[1][n-1][1]);
                dp[0][n][1] = Math.max(dp[0][n-1][0], dp[1][n-1][1]) + arr[0][n];
                // 밑 변 계산
                dp[1][n][0] = Math.max(dp[0][n][0], dp[0][n][1]);
                dp[1][n][1] = dp[1][n-1][0] + arr[1][n];
            }
            System.out.println(Math.max(dp[1][N][0], dp[1][N][1]));
        }
    }
}