[백준] 9465 : 스티커 (JAVA)

문제

BOJ 9465 : 스티커 - https://www.acmicpc.net/problem/9465

풀이

뗄 수 있는 스티커의 점수의 최댓값을 구하는 문제. 한 스티커를 떼면 주변에 붙어있는 스티커들은 망가져 사용할 수 없다.

처음엔 점수가 큰 스티커 순서대로 선택해야하나 생각했는데, 반례가 있어 DP로 풀이해야하는 문제였다.

---

n이 5라면, 다음과 같이 표현할 수 있다. O는 스티커를 의미한다.

	1	2	3	4	5
0	O	O	O	O	O
1	O	O	O	O	O

몇가지 경우를 살펴보자.
1: (0,1) 위치의 스티커를 뗀다면 인접한 (0,2)과 (1,1)은 사용할 수 없게된다.

	1	2	3	4	5
0	O	X	O	O	O
1	X	O	O	O	O

2: (1,1) 위치의 스티커를 뗀다면 인접한 2개 스티커는 사용할 수 없게된다.

	1	2	3	4	5
0	X	O	O	O	O
1	O	X	O	O	O

3: (1,2) 위치의 스티커를 뗀다면 인접한 3개 스티커는 사용할 수 없게된다. 이 경우 1번과 2번 세로줄까지만 생각했을 때, 가장 스티커의 합이 커지는 경우는 (0,1)을 뗀 후 (1,2)을 떼는 경우이다.

	1	2	3	4	5
0	O	X	O	O	O
1	X	O	X	O	O

4: 그렇다면 (0,3)위치의 스티커를 뗀다면 경우의 수는, 아래 2가지가 가능하다.

	1	2	3	4	5
0	O	X	O	X	O
1	X	O	X	O	O

	1	2	3	4	5
0	X	X	O	X	O
1	O	X	X	O	O

이 개념을 DP로 생각한다면 왼쪽 대각선 아래, 왼쪽 대각선 아래의 왼쪽만 확인해서 더 큰 값을 현재 위치에 넣어주면 된다! 4번 경우를 DP로 생각한다면, 이미 dp[1][2]에 (0,1)과 (1,2)의 합이 들어있기 때문에 dp[1][2]와 dp[1][1] 중에 큰 값과 (0,3)값을 더해 dp[0][3]에 저장하면 된다. 이런 식으로 5번 column까지 간 후, 더 큰 값이 결과값이 된다!

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


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

        int tc = Integer.parseInt(br.readLine());

        for (int i = 0; i < tc; i++) {
            int n = Integer.parseInt(br.readLine());

            // initialize
            int[][] stickers = new int[2][n+1];
            int[][] dp = new int[2][n+1];
            for(int j=0; j<2; j++){
                String[] inputs = br.readLine().split(" ");
                for (int k = 1; k <= n; k++) {
                    stickers[j][k] = Integer.parseInt(inputs[k-1]);
                }
            }

	    // 첫번째 column은 자기 자신이 최대이므로 자기 자신으로 초기화
            dp[0][1] = stickers[0][1];
            dp[1][1] = stickers[1][1];

            for (int j = 2; j <= n; j++) {
                dp[0][j] = Math.max(dp[1][j - 1], dp[1][j - 2]) + stickers[0][j];
                dp[1][j] = Math.max(dp[0][j - 1], dp[0][j - 2]) + stickers[1][j];
            }

            System.out.println(Math.max(dp[0][n], dp[1][n]));
        }
    }
}

정리

✔ 알고리즘 분류 - 다이나믹 프로그래밍
✔ 난이도 - ⚪ Silver 2

🤦‍♀️ 오늘의 메모

• DP는 정말 아직도 이해하기가 힘들다ㅠㅠ,, DP문제는 항상 검색해서 풀이과정을 참고해 풀어보게 된다. 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법! 이라는 DP의 취지를 잘 생각해볼 것!

참고 사이트

https://squareyun.tistory.com/5