알고리즘 풀이 - 백준 9465(스티커, DP)

 

관련글

 

Dynamic Programming 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

 

이 문제는 2*n으로 배치된 스티커가 각각 점수가 부여되어 있을 때, 점수합이 최대가 되도록 스티커를 떼는 경우를 찾는 문제이다.

 

 

2. 풀이

 

문제의 예시로 든 스티커를 한 번 그림으로 아래와 같이 살펴보자.

스티커를 뜯게 되면 인접한 다른 스티커도 뜯기고 해당 점수는 Count되지 않게 된다. 그래서 뜯는 경우가 한정되어 있다.

이 문제는 직관적으로 DP로 풀 수 있을 것으로 보인다. 왜냐하면, 좌측에서부터 스티커를 뜯어나간다는 가정을 해볼 때, 다음 스티커를 찢는 경우가 이전의 경우에 영향을 받게 되기 때문이다.

 

실제로, 만약 위 스티커의 배치를 행열로 본다면 2행 5열이라고 볼 수 있을 것이다. 그러면 1행 1열은 50, 2행 1열은 30 이라고 보자.

만약 1열에 위치한 50 또는 30을 떼는 경우를 살펴보면, 50이 가장 큰 점수이니 50이 답이다.
만약 2열에 위치한 10 또는 50을 떼는 경우를 살펴보면, 10을 떼면 1열의 50은 뗄 수 없으니 30+10=40이 최대값이고, 50을 떼면 1열의 30은 뗄 수 없으니 50+50=100이 최대값이되는데, 둘 중 더 큰 값은 100이므로 최종 값은 100이 된다.

이와 같은 방식으로 좌측에서부터 뜯는 과정을 하나의 작은 문제라고 본다면, 그 결과가 그대로 영향을 미치게 되고 그 결과 값을 저장하여 다음 스티커에도 그대로 적용이 가능하니 DP로 풀 수 있다고 볼 수 있다.

 

그러면 State는 어떻게 될까? State는 상태값, 변수인데 행과 열이 각각 변수값이 된다. 왜냐하면 그에 따라 뜯을 수 있는 결과가 달라지기 때문이다.

그러면 상태값이 2개이므로 그 저장하는 배열을 DP[2][N]이라고 하자. N은 열인데, 행은 2개로 고정이므로 좌측과 같이 생성하면 된다.

 

그러면, State의 정의를 한 번 살펴보자.
정의 : DP[i][N] = i행 N번째 스티커를 찢을 때, 가장 최대값이 되는 경우의 점수

 

점화식을 알아보자. 어떻게 될까? 점화식은 현재 1행 N열째 스티커라면 N-1번째의 경우에는 1행의 스티커를 뜯을 수 없고 2행만 가능하다. 

추가로 1행 N열째 스티커라면 N-2번째에 2행을 뜯는 경우가 있을 수 있다.(2행 N-2번째열이면 1행 N-1열을 뜯을 수 없기 때문!).

그림으로 알아보자.

 

따라서 점화식은 아래와 같다. 각 점수는 저장한 배열은 arr[][]이라고 가정.

 

점화식 :
DP[1][N] = MAX(DP[2][N-1] + arr[1][N], DP[2][N-2] + arr[1][N])
DP[2][N] = MAX(DP[1][N-1] + arr[2][N], DP[1][N-2] + arr[2][N])

 

기저 상태는 코드 상으로 0행 0열은 없으니 0으로 초기화가 될 것이고 1열의 경우를 뜯는 경우를 각각 지정 해야한다.
기저 상태 : DP[1][1] = arr[1][1], DP[1][2] = arr[1][2]

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

1) Bottom-up 방식

import java.io.*;

public class Main{
    static int[][] dp;
    static int[][] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int T = Integer.parseInt(br.readLine());
        
        for(int i=0; i < T; i++){
            int n = Integer.parseInt(br.readLine());
            dp = new int[2][n+1];
            arr = new int[2][n+1];
            
            for(int j=0; j < 2; j++){
                String line[] = br.readLine().split(" ");
                for(int k=1; k <= n; k++){
                    arr[j][k] = Integer.parseInt(line[k-1]);
                    
                    // 1열일 때는 바로 저장
                    if(k==1){
                        dp[j][k] = arr[j][k];
                    }
                }
            }
            
            // 열을 우선 모두 계산해가며 우측으로 이동함!
            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];
            }
            
            int result = Math.max(dp[0][n], dp[1][n]);
            bw.write(String.valueOf(result) + "\n");
        }
        
        bw.flush();
        br.close();
    }
}

 

2) Top-Down 방식

import java.io.*;

public class Main{
    static int[][] dp;
    static int[][] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int T = Integer.parseInt(br.readLine());
        
        dp = new int[2][100001];
        arr = new int[2][100001];
        for(int i=0; i < T; i++){
            int n = Integer.parseInt(br.readLine());
            
            // 우선 원 배열 저장 수행
            for(int j=0; j < 2; j++){
                String line[] = br.readLine().split(" ");
                for(int k=1; k <= n; k++){
                    arr[j][k] = Integer.parseInt(line[k-1]);
                    dp[j][k] = -1;
                }
            }
            dp[0][1] = arr[0][1]; dp[1][1] = arr[1][1];
            dp[0][2] = dp[1][1] + arr[0][2]; dp[1][2] = dp[0][1] + arr[1][2];
            
            int result = Math.max(topDown(0, n), topDown(1, n));
            bw.write(String.valueOf(result) + "\n");
        }
        
        bw.flush();
        br.close();
    }
    
    // Top-down 방식, 행을 y, 열을 x로 표현하자
    public static int topDown(int y, int x){
        if(x <= 2 || dp[y][x] >= 0) return dp[y][x]; // 기존의 값이 있는 경우
        
        int temp = (y+1)%2;
        dp[y][x] = Math.max(topDown(temp, x-1), topDown(temp, x-2)) + arr[y][x];
        
        return dp[y][x];
    }
}

Top-Down에서는 주목할 점이 DP배열을 최초 -1로 초기화하였다. 이렇게 하는 이유는 점수가 0점인 카드가 있을 수 있기 때문이다.

점수가 0점이면 topDown 메소드의 제일 윗 줄에서 dp[y][x] > 0으로 했을 때 이미 점수가 있다는 것을 알지 못하고 한 번 더 재귀 호출을 하게 된다! 그래서 부등호로 써준 것이다!

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.