백준

백준 9465 스티커(Java)

Park DJ 2023. 2. 16. 17:31

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

 

9465번: 스티커

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의

www.acmicpc.net


 

Java 코드

 


import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    StringBuilder sb = new StringBuilder();
    
    int t = sc.nextInt();
    
    for(int k = 0; k < t; k++) {
      int n = sc.nextInt();
      int[][] arr = new int[2][n + 1];
      int[][] dp = new int[2][n + 1];
      for(int i = 0; i < 2; i++) {
        for(int j = 1; j <= n; j++) arr[i][j] = sc.nextInt();
      }

      dp[0][1] = arr[0][1];
      dp[1][1] = arr[1][1];

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

      sb.append(Math.max(dp[0][n], dp[1][n])).append("\n");
    }

    System.out.println(sb);
  }
}