[BOJ] 9465번 스티커

개요

다이나믹 프로그래밍을 이용해 풀이하는 문제

문제링크

코드

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

public class Baekjoon9465 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int t = Integer.parseInt(br.readLine());
        int n;
        int[][] sticker;    //스티커 점수 저장
        int[][] dp;         //DP 테이블

        for(int i=0;i<t;i++) {
            n = Integer.parseInt(br.readLine());
            sticker = new int[2][n];
            for(int j=0;j<2;j++) {
                st = new StringTokenizer(br.readLine());
                for(int k=0;k<n;k++) {
                    sticker[j][k] = Integer.parseInt(st.nextToken());
                }
            }
            dp = new int[2][n+1];

            dp[0][1] = sticker[0][0];   //DP 테이블 초기값 설정
            dp[1][1] = sticker[1][0];   //DP 테이블 초기값 설정
            for(int j=2;j<=n;j++) {
                dp[0][j] = Math.max(dp[1][j-1], dp[1][j-2]) + sticker[0][j-1];
                dp[1][j] = Math.max(dp[0][j-1], dp[0][j-2]) + sticker[1][j-1];
            }
            bw.write(Math.max(dp[0][n], dp[1][n])+"\n");
        }
        bw.flush();
    }
}

해결 과정

스티커를 하나 떼면 상하좌우로 못쓰게 된다.

초록색 부분을 떼면 빨간색 부분을 못쓰고 그다음으로 뗄 수 있는 가장 근접부분은 주황색 부분이다.

하지만 주황색 100부분은 주황색 50부분을 떼도 뗄 수 있는 부분이기 때문에

떼어낸 스티커의 대각선 부분이 다음으로 뗄만한 스티커라고 할 수 있다.

하지만 언제나 대각선만 떼는 것이 최대값인가 하면 아니다.

위 사진의 예처럼 대각선 부분의 합이 최대값이 아닐 수 있다.

그래서 확인 해봐야하는 것이 가장 가까운 대각선과 그옆에 있는 칸이다.

자기자신을 기준으로 대각선방향 2칸을 확인해 둘 중에 더 값이 높은 것을 택하면 최대값이 나온다.

이것을 식으로 만들어보면 다음과 같다.

DP[ 0 ][ j ] = MAX( DP[ 1 ][ j - 1 ], DP[ 1 ][ j - 2 ] ) + sticker[ 0 ][ j ]

그러면 DP 테이블을 보자

점화식에 의하면 두칸이전의 값도 비교해야 되므로 DP테이블의 열은 0부터 시작한다.

그리고 1번째 열은 무조건 점수가 고정됨으로 그냥 넣어주고 2번째 열부터 점화식으로 계산해간다.

따라서 260이 최대값이 나온다.

결과