[Algorithm] 스티커

이번 문제는 최댓갑을 출력하는 문제다. 여타 DP문제와 다를 바 없지만 조금 헷갈렸던

부분은 2차원 배열에 대한 조건이였다. 이 문제를 해결할 수 있는 아이디어는 각각의

열에 대한 값을 구하는 것이였다. 각 열에 대하여 윗 스티커를 선택했을 때, 아래스티커를

선택했을때, 둘다 안했을때에 대한 값을 구한 후 마지막 세가지 경우에 대해서 최댓값을

구함으로써 해결하였다. 점화식은 다음과 같다.

각각의 케이스에 대하여 d[N][0]은 N열에 대하여 스티커를 고르지 않은 경우 , d[N][1]은

N열에 대하여 윗 스티커를 고른 경우 , d[N][2]는 N열에 대하여 아래스티커를 고른경우이다

소스코드 :
package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class a_9465 {

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
int K = Integer.parseInt(br.readLine());
int[][] V = new int[K][2];
int[][] d = new int[K][3];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int k = 0;
while (st.hasMoreTokens()) {
V[k][0] = Integer.parseInt(st.nextToken());
k++;
}
st = new StringTokenizer(br.readLine(), " ");
k = 0;
while (st.hasMoreTokens()) {
V[k][1] = Integer.parseInt(st.nextToken());
k++;
}
// 입력 완료
d[0][0] = 0;
d[0][1] = V[0][0];
d[0][2] = V[0][1];

for (int j = 1; j < K; j++) {
d[j][0] = Math.max(d[j - 1][1], d[j - 1][2]);
d[j][1] = Math.max(d[j - 1][2], d[j - 1][0]) + V[j][0];
d[j][2] = Math.max(d[j - 1][1], d[j - 1][0]) + V[j][1];
}
System.out.println(Math.max(d[K - 1][1], d[K - 1][2]));
}

}

}