백준 9465 스티커_DP

 

문제 : 

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

 

 

접근 : 

 

 - 위쪽을 뜯는 경우와 아래쪽을 뜯는 경우를 나눠서 생각한다.

 

 - 가로의 위치가 0 과 1 인 경우에는 나올 수 있는 최대값을 dp에 저장한다.

 

 - 가로의 위치가 2 이상인 경우에는 위쪽과 아래쪽을 나눠서 현재 위치까지 도달했을 때, 가능한 최대값을 dp에 저장한다.

 

 - 가로로 진행할 때, 항상 위쪽과 아래쪽을 나누어 더 큰 값으로 ans 값을 갱신한다.

 

 - n-1 까지 진행한 후, ans 값을 출력한다.

 

 

 

 

 

 

 

코드구현 : 

 

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        for (int i=0 ; i < t ; i++) {
            int n = Integer.parseInt(br.readLine());

            int [][] map = new int[2][n];
            long [][] dp = new long[2][n];
            long ans = 0;

            for(int j = 0 ; j < 2 ; j++){
                String[] temp = br.readLine().split(" ");
                for (int k = 0; k < n; k++) map[j][k] = Integer.parseInt(temp[k]);
            }

            dp[0][0] = map[0][0];
            dp[1][0] = map[1][0];
            ans = Math.max(ans, Math.max(dp[0][0], dp[1][0]));

            if(n == 1) {
                sb.append(String.format("%d %n", ans));
                continue;
            }

            dp[0][1] = dp[1][0] + map[0][1];
            dp[1][1] = dp[0][0] + map[1][1];
            ans = Math.max(ans, Math.max(dp[0][1], dp[1][1]));

            for(int j = 2 ; j < n ; j++){
                dp[0][j] = Math.max(dp[1][j-2], dp[1][j-1]) + map[0][j];
                dp[1][j] = Math.max(dp[0][j-2], dp[0][j-1]) + map[1][j];
                ans = Math.max(ans, Math.max(dp[0][j], dp[1][j]));
            }
            sb.append(String.format("%d %n", ans));
        }
        System.out.println(sb);
        br.close();
    }
}