[알고리즘_풀이] DP문제, 백준 9465번 스티커

스티커는 2행 n열로 주어진다.

하나를 떼면 왼쪽, 오른쪽, 위, 아래를 연속으로 뗄 수 없다. 따라서 왼쪽부터 오른쪽으로 스티커를 뗄 수 있으면서 그 값이 최댓값인 것을 경우의 수 중에서 고를 것이다.

 

생각

각각 열마다 3가지 경우의 수를 둘 것이기 때문에 이렇게 할당했다.

int[][] d = new int[n+1][3]; 

d[i][0] = i열에서 하나도 안뗐을 때, 그전부터 이 상황((k=1; k<=i; k++), 1열부터 i열까지)까지 더한 값.

              -> '그 전부터 이 상황까지'의 부분이 dp가 적용되어야할 부분.

d[i][1] = i열에서 위에꺼만 뗐을 때, 그전부터 이 상황까지 더한 값.

d[i][2] = i열에서 아래꺼만 뗐을 때, 그전부터 이 상황까지 더한 값.

 

-> 결국 마지막 열에서 d[n][0], d[n][1], d[n][2]의 최댓값을 구하면 답.

 

 

GET 점화식

 

 

 

코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();

        for(int t=0; t<T; t++) {
            int n = scan.nextInt();
            int [][] sticker = new int[n+1][2];
            int [][] d = new int[n+1][3];

            for(int i=0; i<2; i++) {
                for(int j=1; j<=n; j++) {
                    sticker[i][j] = scan.nextInt();
                }
            }

            // i는 왼쪽에서 시작해서 오른쪽으로 향하는 방향으로 증가 (i=0; i<n; i++)
            // X : 뜯지 않음. O : 뜯음.
            // d[i][0] -> i열까지 스티커 둘다 안뜯음. X X  -> 그랬을 때 얻은 점수
            // d[i][1] -> i열에 스티커 위꺼만 뜯음. O X  -> 그랬을 때 얻은 점수
            // d[i][2] -> i열에 스티커 아래꺼만 뜯음.X O  -> 그랬을 때 얻은 점수

            d[1][0] = 0; //X X
            d[1][1] = sticker[0][1]; //O X
            d[1][2] = sticker[1][1]; //X O

            for(int i=2; i<=n; i++) {
                d[i][0] = Math.max(d[i-1][0], Math.max(d[i-1][1], d[i-1][2])); // 지금 i에서 하나도 안뜯었으면 전꺼는 뭐가되든 상관없음. 3개 다 비교해서 큰 값 넣기.
                d[i][1] = Math.max(d[i-1][0], d[i-1][2])+sticker[0][i];        // i열의 위에꺼를 뗌. 전꺼는 안떼거나(0) 밑에꺼(2) 뗴야함. 그리고 i 자신을 뗀 것을 더함. 0이 위에꺼니까 sticker[0][i]을 더한다.
                d[i][2] = Math.max(d[i-1][0], d[i-1][1])+sticker[1][i];        // i열의 아래꺼를 뗌. 전꺼는 안떼거나(0) 위에꺼(1) 떼야함. 그리고 i 자신을 뗸 것을 더함. 1이 아래꺼니까 sticker[1][i]을 더한다.
            }

            // 결국 마지막열에 해당하는 값이 구하는 답이다.
            System.out.println(Math.max(d[n][0], Math.max(d[n][1], d[n][2])));
        }
    }
}

 

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

9465번: 스티커