CS/알고리즘_문제풀이(자바)

스티커

Jedy_Kim 2021. 10. 13. 20:15
728x90

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

 

9465번: 스티커

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

www.acmicpc.net

 

// 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.*;
import java.io.*;
 
public class Main{ 
   
  // main
  public static void main(String[] args) throws Exception {
    
    StringBuilder sb   = new StringBuilder();
    BufferedWriter bw  = new BufferedWriter(new OutputStreamWriter(System.out));
    BufferedReader br  = new BufferedReader(new InputStreamReader(System.in)); 
    
    int t = Integer.parseInt(br.readLine());
    for(int i=0; i<t; i++) {
      int n = Integer.parseInt(br.readLine());
      int[][] arr = new int[2][n+1];
      int[][] dp  = new int[2][n+1];
      
      for(int j=0; j<2++j) {
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int k=1; k<=n; ++k) {
          arr[j][k] = Integer.parseInt(st.nextToken());
        }
      }
      
      dp[0][1= arr[0][1];
      dp[1][1= arr[1][1];
      for(int j=2; j<=n; j++) {
        dp[0][j] = Math.max(dp[1][j-2], dp[1][j-1]) + arr[0][j];
        dp[1][j] = Math.max(dp[0][j-2], dp[0][j-1]) + arr[1][j];
      }
      
      int result = Math.max(dp[0][n], dp[1][n]);
      sb.append(result + "\n");
    }
    
    bw.write(sb.toString());
    br.close();
    bw.flush();
    bw.close();
  } 
}
 
cs

 

반응형

'CS > 알고리즘_문제풀이(자바)' 카테고리의 다른 글

알고스팟  (0) 2021.10.14
웰컴  (0) 2021.10.14
이친수  (0) 2021.10.13
암호 만들기  (0) 2021.10.13
A+B - 2  (0) 2021.10.13