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

DP...

설명하기 귀찮은데..

DP중에 쉬운문제같다. 직관적으로 보여.

풀이

배열의 위치마다 값을 저장해야하는 arr[][] 배열이 필요하고 

이전값과 함해서 최대값을 만들기 위한 dp[][] 배열이 필요하다.

이경우에 올 수 있는 경우는

1. 자신의 왼쪽 대각선 (위의 배열일 경우 왼쪽 아래, 아래 배열일 경우 왼쪽 위) 에 존재하는 값 다음에 올 수 있고

2. 자신의 왼쪽 왼쪽 에 위치한 값 다음에 올 수 있다.

이 두 값 다음에 오는거 말고는 최대값을 가질 수 없을 거같은데..?

아무튼 두 경우를 이용해 식을 만들면

dp[i][0] = Math.max(dp[i-1][1],dp[i-2][1] ) + arr[i][0];

dp[i][1] = Math.max(dp[i-1][0],dp[i-2][0] ) + arr[i][1];

형식으로 나온다. 이거 대로 써주면 끄읏.

소스

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
 
public class Main {
 
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        // BufferedReader br = new BufferedReader(new
        // InputStreamReader(System.in));
 
        int Testcase = Integer.parseInt(br.readLine());
        int[][] arr;
        int[][] dp;
        String[] str;
        for (int t = 0; t < Testcase; t++) {
            int N = Integer.parseInt(br.readLine());
            arr = new int[N+1][2];
            dp = new int[N+1][2];
            for (int i = 0; i < 2; i++) {
                str = br.readLine().split(" ");
                for (int j = 1; j <=N; j++) {
                    arr[j][i] = Integer.parseInt(str[j-1]);
                }
            }
            
            dp[1][0] = arr[1][0];
            dp[1][1] = arr[1][1];
            for(int i=2; i<=N; i++){
                dp[i][0] = Math.max(dp[i-1][1],dp[i-2][1] ) + arr[i][0];
                dp[i][1] = Math.max(dp[i-1][0],dp[i-2][0] ) + arr[i][1];
            }
            System.out.println(Math.max(dp[N][0], dp[N][1]));
        }
    }
}