백준 9465 스티커 / JAVA

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

9465번: 스티커

 

> 풀이

 

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

/*
 * 백준 9465 스티커
 * #골드5
 * #DP
 */

public class boj_9465 {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		while(T-- > 0) {
			int n = Integer.parseInt(br.readLine());
			int[][] arr = new int[2][n+1]; // 1, 2, 3, 4, ,, n 까지 편의상쓰기위함
			int[][] dp = new int[2][n+1];
			
			// 초기화
			for(int i = 0; i < 2; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for(int j = 1; j <= n; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			// 맨 앞 초기화
			dp[0][1] = arr[0][1];
			dp[1][1] = arr[1][1];
			
			// DP로 최댓값 구하기
			for(int k = 2; k <= n; k++) {
				dp[0][k] = Math.max(dp[1][k-1], dp[1][k-2]) + arr[0][k];
				dp[1][k] = Math.max(dp[0][k-1], dp[0][k-2]) + arr[1][k];
			}
			
			System.out.println(Math.max(dp[0][n], dp[1][n]));
		}
	}
}