[Baekjoon] 스티커 - Java

문제

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

 

풀이

2행 n열로 배치된 스티커를 떼서 얻을 수 있는 점수의 최댓값을 구하는 문제이다.

 

일단 2문제에서 떼고 안떼보고 전체적인 완탐을 수행하면  2^100000이기 때문에 무조건 시간초과가 난다.

 

그러면 이 문제를 어떻게 해결할 수 있을까?

 

결국 10만개의 데이터가 있다는 것은 선형적인 시간복잡도를 가지는 것으로 해결해야한다.

 

다이나믹 프로그래밍을 이용한다.

이전 열까지 스티커를 떼고 최댓값을 누적시키면서 갱신해보는 것이다.

 

만약에 이런 형태가 있다고 하자.(O: 뗀 스티커, X: 떼지 않은 스티커)

XXO

XXX

 

그러면 하단의 2가지가 된다. (?는 스티커가 붙여있는지 안붙여있는지 모른다는 의미이다.)

?XO

OXX

 

?XO

XOX

 

즉 밑에 있는 행에서 현재 열에서 -1, -2를 한 열의 최댓값에서(arr[1][i - 1], arr[1][i - 2]) 현재 위치의 스티커 값을 더하면 뗀 스티커의 최댓값이 되는 것이다.

 

그러면 ?위치에 있는 것은 왜 최댓값을 고려하지 않을까?

4개의 열을 그려보면 정답을 알 수 있다.(C는 현재 열이다)

OXXC

XXOC

 

XOXC

XXOC

 

?위치를 고려하지 않은 이유는 이미 이전 열에서 최댓값을 ?자리와 비교해서 갱신이 되었기 때문이다.

 

?XO

XOX

즉 이 경우에서 이미 최댓값이 갱신되었다. 그러므로 고려하지 않아도 된다.

 

1. 테이블을 정의한다.

dp[i][j] = i행, j열에서 뗄 수 있는 스티커의 최대 점수

 

2. 우리가 원하는 답을 구할 수 있는지 생각해본다.

결국 우리가 원하는 답은 j열에 있는 최대 점수들 중 최댓값을 구하면 된다.

 

3. 정의한 테이블을 어떻게 초기화할 것인지 생각해본다.

첫번째 열인 경우, 무조건 자신의 점수가 최댓값이 된다.

dp[0][1] = scores[0][1]

dp[1][1] = scores[1][1]

 

4. 점화식을 정의한다.

i >= 2일때,

dp[0][i] = max(dp[1][i - 1], dp[1][i - 2]) + 현재 위치 점수

dp[1][i] = max(dp[0][i - 1], dp[0][i - 2]) + 현재 위치 점수

 

소스코드

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

import java.util.StringTokenizer;

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

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

        StringTokenizer st = null;

        StringBuilder sb = new StringBuilder();

        while (t > 0) {
            int n  = Integer.parseInt(br.readLine());

            int[][] scores = new int[2][n + 1];
            int[][] dp = new int[2][n + 1];

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

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

            dp[0][1] = scores[0][1];
            dp[1][1] = scores[1][1];

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

            sb.append(Math.max(dp[0][n], dp[1][n])).append("\n");

            t--;
        }

        System.out.print(sb);

        br.close();
    }
}

 

실행결과