백준 9465 / 스티커

문제

풀이

설명

D[i][j] = 2×i 에서 얻을 수 있는 최대 점수, i번 열에서 뜯는 스티커는 j

• j = 0 -> 뜯지 않음
• j = 1 -> 위쪽 스티커를 뜯음
• j = 2 -> 아래쪽 스티커를 뜯음

D[i][j] = 2×i 에서 얻을 수 있는 최대 점수, i번 열에서 뜯는 스티커는 j

• 뜯지 않음 (D[i][0])
i-1 열에서 스티커를 어떻게 뜯었는지 상관이 없다
max(D[i-1][0], D[i-1][1], D[i-1][2])
• 위쪽 스티커를 뜯음 (D[i][1])
i-1열에서 위쪽 스티커는 뜯으면 안된다
max(D[i-1][0], D[i-1][2]) + A[i][0]
• 아래쪽 스티커를 뜯음 (D[i][2])
i-1열에서 아래쪽 스티커는 뜯으면 안된다
max(D[i-1][0], D[i-1][1]) + A[i][1]

코드

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

public class Num9465 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.valueOf(br.readLine());
        while (t-- > 0) {
            int n = Integer.valueOf(br.readLine());
            long[][] a = new long[n+1][2];
            {
                String[] line = br.readLine().split(" ");
                for (int i=1; i<=n; i++) {
                    a[i][0] = Long.valueOf(line[i-1]);
                }
            }
            {
                String[] line = br.readLine().split(" ");
                for (int i=1; i<=n; i++) {
                    a[i][1] = Long.valueOf(line[i-1]);
                }
            }
            long[][] d = new long[n+1][3];
            for (int i=1; i<=n; i++) {
                d[i][0] = Math.max(d[i-1][0],Math.max(d[i-1][1],d[i-1][2]));
                d[i][1] = Math.max(d[i-1][0],d[i-1][2])+a[i][0];
                d[i][2] = Math.max(d[i-1][0],d[i-1][1])+a[i][1];
            }
            long ans = 0;
            ans = Math.max(d[n][0], Math.max(d[n][1], d[n][2]));
            System.out.println(ans);
        }
	}
}

코드설명

참고 :
출처 : https://www.acmicpc.net/problem/9465