일단 시작해보는 블로그

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

CS/알고리즘 풀이

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

사용자 Selina Park 2019. 9. 16. 13:40

스티커는 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번: 스티커

문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점

www.acmicpc.net

 

0 Comments
댓글쓰기 폼