[백준] 9465 스티커 - Dynamic Programming / Java

• 문제 링크

9465번: 스티커

 

• 풀이 과정

2차원 dp배열을 생성하고, 문제에 주어진 행과 열의 정보에 따라 dp[2][n + 1] 의 크기로 생성한다.

 

문제에 주어진 조건에 의해 특정 스티커를 선택할 경우 해당 스티커의 상하좌우는 선택할 수 없으며,

탐색을 왼쪽에서 오른쪽으로 수행할 것이기 때문에 선택한 스티커의 오른쪽 또한 선택할 수 없게 되는 것에 초점을 둔다.

 

특정 스티커를 선택하기 위해서는 해당 스티커의 왼쪽 대각선 방향의 첫번째, 또는 두번째 중 하나만을 선택해야 하므로

그 둘의 누적된 값을 비교하여 큰 값을 현재 선택된 스티커의 값에 더한다.

 

이를 코드로 나타내면,

상단의 스티커를 선택할 시 dp[0][i] += Math.max(dp[1][i - 1], dp[1][i - 2]),

하단의 스티커를 선택할 시 dp[1][i] += Math.max(dp[0][i - 1], dp[0][i - 2]) 로 나타낼 수 있다.

 

이렇게 구해진 상단과 하단의 값을 비교하여(Math.max(dp[0][n], dp[1][n])) 최대값을 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

    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());

        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            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++)
                    dp[i][j] = Integer.parseInt(st.nextToken());
            }

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

            bw.write(Math.max(dp[0][n], dp[1][n]) + "\n");
        }

        bw.flush();
    }

}