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

인간몽쉘김통통·2023년 12월 15일

다이나믹 프로그래밍 백준 알고리즘

백준

목록 보기

31/92

문제

이해

2 x N 으로 이루어진 공간 안에 스티커의 점수가 저장되어 있다. 이 때, 각 스티커를 선택하고자 한다.

하나의 스티커를 선택하면 선택된 스티커의 상하좌우 인접한 스티커는 선택할 수 없다.

위와 같은 규칙으로 스티커를 선택할 때 스티커 집합의 점수 합의 최댓값을 출력한다.

접근

가장 단순하게 생각할 수 있는 방법은 BFS로 완전탐색을 실행하는 것이다.

스티커 공간은 행이 2로 고정되어 있고 열이 입력에 따라 달라진다.

최초 0열에서 선택할 수 있는 스티커는 0행, 1행 스티커이다.

만일, 0열에서 0행 스티커가 선택되면 그 다음으로 가능한 스티커는 다음과 같다.

1열 1행
2열 0행
2열 1행

(노란색 셀 -> 선택됨)
(초록색 셀 -> 선택가능한 후보)

그렇다면 셀을 선택할 때마다 가능한 경우로 뻗어나가 BFS로 완전탐색을 하고 각 경우의 끝에서 최댓값을 갱신하면 해결가능하다.

하지만 주어진 N의 값은 최대 100,000이다. 100,000개의 열을 완전탐색하려면 시간초과가 발생한다.

따라서, 완전탐색이 아닌 메모이제이션을 이용한 DP로 풀이하는 것이 더 좋아보인다.

$A_n$ 을 n번째에서의 최댓값이라 가정해보자.

n번째에서 0행을 선택할지 1행을 선택할지는 n-1번째의 선택에 따라서 달라진다.

이 말은 n번째에서 어떤 행을 선택하는냐에 따라서 그전에 구했던 $A_(n-1)$ 이 쓸모 없을 수도 있다는 의미이다.

(n번째에서 0행을 선택한다고 할때 최대의 경우 n-1에서 1행 혹은 선택하지 않았다는 보장이 없음)

따라서, 특정 열에서 0행을 선택했을 때, 1행을 선택했을 때의 경우의 최댓값을 각각 구해서 메모이제이션에 활용할 필요가 있다.

이를 위해 배열을 2가지 생성하였다.
1. max_select0[N+1] (i번째에서 0행을 선택했을 때의 최댓값)
2. max_select1[N+1] (i번째에서 1행을 선택했을 때의 최댓값)

그렇다면 배열의 i번째 값은 어떻게 구할 수 있을까? 점화식은 다음과 같다.

max_select0[i] = max_select1[i-1] + val[i]
= max_select1[i-2] + val[i] (i >= 2)

i번째에서 0행을 선택할 때 가능한 경우는 위와 같이

i-1에서 1을 선택
i-2에서 1을 선택, i-1에서 선택x

두 가지 존재한다. 이는 1행을 선택하는 경우도 마찬가지이다.

따라서, max_select0, max_select1 의 0과 1만 최초에 초기화한뒤 bottom_up 방식으로 다이나믹 프로그래밍을 수행시키면 끝에서 max_select0[N], max_select1[N]을 구할 수 있다.

N열에서 가능한 경우는 0과 1을 선택하는 두 가지 경우 뿐이기에 이를 비교하여 큰 값을 출력하면 된다.

코드

package java_baekjoon;

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

public class prob9465 {
    static int N;
    static int[][] sticker;
    static int[] max_select0;
    static int[] max_select1;

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

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

        while (T-- > 0) {
            N = Integer.parseInt(br.readLine());
            max_select0 = new int[N + 1];
            max_select1 = new int[N + 1];

            sticker = new int[2][N + 1];

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

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

            max_select0[0] = 0;
            max_select1[0] = 0;
            max_select0[1] = sticker[0][1];
            max_select1[1] = sticker[1][1];

            for(int i=2;i<=N;i++){
                max_select0[i] = Math.max(max_select1[i-1], max_select1[i-2]) + sticker[0][i];
                max_select1[i] = Math.max(max_select0[i-1], max_select0[i-2]) + sticker[1][i];  
            }

            System.out.println(Math.max(max_select0[N], max_select1[N]));
        }
    }

}