[백준] 9465 스티커 자바(Java)

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

9465번: 스티커

 

문제에서 이동하는 방법은 현재 위치에서 대각선으로만 갈 수 있다.

하지만 아래 그림과 같이 그 다음칸의 대각선으로도 이동이 가능하다.

1번 값과, 2번 값중 큰 값을 선택하면 된다.

 

그럼 점화식나온다.

dp[0][n] = Max(dp[1][n - 1], dp[1][n - 2]) + dp[0][n]

dp[1][n] = Max(dp[0][n - 1], dp[0][n - 2]) + dp[1][n]

 

자바 코드

package main.iyk2h;

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

public class Main {

    static int[][] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for (int i = 0; i < input; i++) {
            int n = Integer.parseInt(br.readLine());
            dp = new int[2][n + 1];

            for (int val = 0; val < 2; val++) {
                String[] arr = br.readLine().split(" ");
                for (int j = 1; j <= n; j++) {
                    dp[val][j] = Integer.parseInt(arr[j - 1]);
                }
            }

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

            // 점수의 합의 최대값 출력
            System.out.println(Math.max(dp[0][n], dp[1][n]));
        }
    }
}