[백준] 9465. 스티커

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

9465번: 스티커

 

풀이

주어진 N 값에 따라 가로의 길이가 결정되는 형태이므로 아래 코드와 같이 열을 기준으로 점화식을 세울 수 있었다.

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

 

 

설명하자면, dp배열에서 dp[0][j]을 계산하려면 dp[1][j - 1]과 dp[1][j - 2]를 비교하여 둘 중 큰 값을 선택한 뒤 point[0][j]을 더해주는 것이다.

 

처음에는 

1. dp[0][j - 2] 와 dp[1][j - 2] 중 최댓값을 가려내고

2. 그 값을 또 dp[1][j - 1] 과 비교하여 최댓값을 가려낸 뒤

3. point[0][j] 를 더해준다

이런 흐름이어야 하지 않나 생각했었다.

 

하지만 dp[0][j - 2]를 선택했을 때 dp[0][j - 1]은 무조건 선택하게 되므로 이 경우의 계산은 dp[1][j - 1]에 반영된다. 

그러므로 dp[1][j - 2]와 dp[1][j - 1]만 비교하여 dp[0][j] 값 계산에 반영하면 된다.

 

코드

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

public class BOJ9465 {

    static int dp[][], point[][];

    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());  // 스티커의 가로 길이

            point = new int[2][N + 1];  // 각 위치의 포인트
            dp = new int[2][N + 1];  // 각 위치까지의 최댓 점수

            // 배열 입력
            StringTokenizer st;
            for (int j = 0; j < 2; j++) {
                st = new StringTokenizer(br.readLine());
                for (int k = 1; k <= N ; k++) {
                    point[j][k] = Integer.parseInt(st.nextToken());
                }
            }

            // 기저 사례
            dp[0][1] = point[0][1];
            dp[1][1] = point[1][1];

            // 현재 위치의 대각선 값과 그 왼쪽 값을 비교
            for (int j = 2; j <= N; j++) {
                // 점화식
                dp[0][j] = Math.max(dp[1][j - 1], dp[1][j - 2]) + point[0][j];
                dp[1][j] = Math.max(dp[0][j - 1], dp[0][j - 2]) + point[1][j];
            }

            System.out.println(Math.max(dp[0][N], dp[1][N]));
        }
    }
}