200922 화 [BOJ] 9465

BOJ 9465

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

public class Main {	

    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	
    	int T = Integer.parseInt(br.readLine());
    	int[][] dp;
    	int[][] cost;

    	for(int i=0;i<T;i++) {
    		int N = Integer.parseInt(br.readLine());
    		
    		cost = new int[2][N+1];
    		dp = new int[2][N+1];
    		
    		for(int j=0;j<2;j++) {
    			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    			int k = 1;
    			while(st.hasMoreTokens()) {
    				cost[j][k] = Integer.parseInt(st.nextToken());
    				k++;
    			}
    		}
    		
    		dp[0][1] = cost[0][1];
    		dp[1][1] = cost[1][1];
    		for(int k=2;k<=N;k++) {
    			dp[0][k] = Math.max(dp[1][k-1], dp[1][k-2]) + cost[0][k];
    			dp[1][k] = Math.max(dp[0][k-1], dp[0][k-2]) + cost[1][k];
    		}
    		bw.write(String.valueOf(Math.max(dp[0][N], dp[1][N])));
    		bw.flush();
    		bw.newLine();
    	}
    	br.close();
    	bw.close();
    }
}

(참고 : https://fbtmdwhd33.tistory.com/76 )
결국 다른 사람 풀이를 보고 이해했다. 아니, 사실 아직도 잘 이해가 안된다.
소스는 이해를 했는데, 어떻게 저 원리가 성립되는지 잘 모르겠다.
DP 진짜 알듯말듯 어렵네..

BufferedReader + BufferedWriter 를 사용했을 때, Scanner + System.out.println()의 시간보다 1/2 정도로 단축되었고,
단순히 System.out.println() 말고 bw.newLine()으로 작성한거에서 16ms가 단축되는 현상도 발견했다.