[백준][9465번] 스티커

문제 URL

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

나의 풀이

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int MAX_SIZE = 100000;
    public static void main(String args[]) throws IOException {
        StringTokenizer str = new StringTokenizer(br.readLine());
        int size = Integer.parseInt(str.nextToken());
        int[][] arr = new int[3][MAX_SIZE+1];
        //d[i][j] : 마지막은 j를 칠한 i번째 줄까지 점수의 총합
        // 값 j: 아무것도 칠하면 0, 윗칸은 1, 아랫칸은 2
        int[][] d = new int[MAX_SIZE+1][3];
        while(size-- > 0){
            str = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(str.nextToken());
            for(int i=1; i<=2; i++){
                str = new StringTokenizer(br.readLine());
                for(int j=1; j<=n; j++){
                    arr[i][j] = Integer.parseInt(str.nextToken());
                }
            }
            for(int i=1; i<=n; i++){
                d[i][0] = Math.max(Math.max(d[i-1][0], d[i-1][1]),d[i-1][2]);
                d[i][1] = arr[1][i] + Math.max(d[i-1][0],d[i-1][2]);
                d[i][2] = arr[2][i] + Math.max(d[i-1][0],d[i-1][1]);
            }

            int ans = Math.max(Math.max(d[n][0], d[n][1]),d[n][2]);
            bw.write(ans+" ");
            bw.newLine();
        }
        bw.flush();
        bw.close();
    }
}

느낀점

시간복잡도 : O(N)

---