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

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

9465번: 스티커

🔍 Solve

다이나믹 프로그래밍으로 풀기 전, 완전 탐색으로 풀었을 때 시간 초과가 났던 문제입니다.

완전 탐색으로 풀었을 때 우선순위가 큰 것부터 선택하고 인접한 곳들을 지우는 방법으로 풀었습니다.

isSelect배열을 선언하여 지워지는 곳은 1로, 선택된 곳은 2로 저장하였고, isSelect배열이 0이 아닌 수로 꽉 차면 break를 해주었습니다. 해당 방법은 테스트 케이스는 맞으나 시간 초과로 통과하지 못했습니다.

 

따라서 다이나믹 프로그래밍 방법을 사용하였습니다.

dp배열로 현재 위치까지 계산될 수 있는 값 중 가장 큰 값을 저장하였습니다.

현재 위치 기준으로 dp [row-1][col-1]과 dp [row-1][col-2]의 누적 값 중 큰 값을 dp [row][col]에 저장합니다.

 

N위치까지 다 돌았으면 마지막에 dp[0][N]과 dp [1][N] 중 큰 값을 답으로 채택했습니다.

 

❗ Code

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

public class BOJ_S1_9465_스티커 {
    static int N;
    static int [][] stickers;
    static int [][] dp;

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

        int T = Integer.parseInt(br.readLine());
        for(int t=1;t<=T;t++){
            N = Integer.parseInt(br.readLine());
            stickers = new int[2][N+1];
            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++){
                    stickers[i][j] = Integer.parseInt(st.nextToken());
                    dp[i][j] = stickers[i][j];
                }
            }
            for(int j=2;j<=N;j++){
                dp[0][j] = stickers[0][j]+Math.max(dp[1][j-1], dp[1][j-2]);
                dp[1][j] = stickers[1][j]+Math.max(dp[0][j-1], dp[0][j-2]);
            }
            sb.append(Math.max(dp[0][N], dp[1][N])).append("\n");
        } //t
        System.out.println(sb);
    }
}