9465 스티커

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

문제 이해

완전탐색으로도 정답은 구할 수 있지만, n의 최댓값은 100,000이므로 시간제한에 걸리게 된다.

DP로 풀기 위해 점화식을 찾아보자.

떼어낸 스티커의 상하좌우에 있는 스티커는 사용할 수 없다.

우선 간단히 생각해보면 다음 그림과 같이 대각선을 반복하는 2가지의 경우가 나온다.

이 두 가지의 경우에서 최댓값은 250이지만, 이는 전체 경우의 수에서 최댓값이 아니다.

스티커를 선택하지 않는 경우가 있기 때문이다.

다음 그림처럼 100 다음 열인 3열의 스티커를 선택하지 않는다면, 60인 스티커를 선택할 수 있어 260으로 최댓값을 구할 수 있다.

100 다음 한 열을 건너뛰고 40을 선택하는 경우는 항상 최댓값을 구할 수 없다.

10을 선택해도 40을 고를 수 있기 때문이다.

따라서 한 열을 건너뛰려면 대각선에 있는 스티커를 골라야 한다.

그렇다면 두 개의 열을 건너뛰는 경우는 어떨까?

[1][1]에 있는 50 스티커를 선택한 뒤 두 개의 열을 건너뛰고, [0][4]의 스티커를 선택한다고 생각해 보자.

이렇게 두개의 열을 건너뛰는 경우 역시 항상 최댓값이 나오지 않는다.

[][4] 이전의 스티커인 [][2] or [][3]을 선택해도 [][4]를 선택할 수 있기 때문에, [][4] 이전의 스티커를 챙기는 게 항상 값이 크기 때문이다.

따라서 스티커 한 열을 건너뛰는 경우만 고려하면 된다.

다음 사진처럼 [1][4]에 있는 스티커 60을 선택하는 경우는 두 가지이다.

[0][2]의 스티커 100을 선택하고 바로 [1][4]를 선택하는 경우
[0][3]의 스티커 20을 선택하고 [1][4]를 선택하는 경우

만약 [0][4]의 스티커 40을 선택하는 경우는 이 반대인 [1][2], [1][3]을 고려하면 될 것이다.

val[][] 배열을 현재 스티커까지의 최대 점수 합이라고 생각하면 다음과 같은 식을 도출할 수 있다.

→ val[1][4] = MAX( val[0][3], val[0][2] ) + sticker[1][4]

다른 스티커 역시 이와 같은 경우를 고려하면 된다.

따라서 점화식은 다음과 같다

val[row][col] = MAX( val[다른 row][col-1], val[다른 row][col-2] ) + sticker[row][col]

코드

stickers는 각 스티커의 가치를 저장하고, values는 현재 스티커까지의 최댓값을 저장한다.

계산의 편의를 위해 맨 앞에 아무것도 선택하지 않은 열을 추가했다. (n+1 개 열)

→ col-2를 바로 계산 가능하다.

첫 열의 스티커는 자기 자신이 항상 최댓값이므로 초기화 해주었다.

import java.io.*;

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

        for (int i = 0; i < T; i++) {
            int n = Integer.parseInt(br.readLine());
            int[][] stickers = new int[2][n+1];
            int[][] values = new int[2][n+1];

						// stickers 배열 초기화
            for (int j = 0; j < 2; j++) {
                String[] split = br.readLine().split(" ");
                for (int k = 1; k <= n; k++) {
                    stickers[j][k] = Integer.parseInt(split[k-1]);
                }
            }

						// 첫 열의 스티커 초기화
            values[0][1] = stickers[0][1];
            values[1][1] = stickers[1][1];

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

저작자표시