[Baekjoon]9465.스티커(DP)

Baekjoon 

#9465. 스티커

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

---

처음에 문제를 보고 완전탐색으로 풀 수 있겠다고 생각했지만 알고리즘 분류에 DP로 되어 있어서 DP로 풀기로 했다.

완전탐색으로 풀어보고 비교해봐야겠다. 일단 DP를 이용해서 풀자.

문제에서 모서리를 공유하며 인접한 스티커는 뗄 수 없다고 했다. DP로 풀기 위해 N번째 열의 상태와 N-1번째 열의 상태를 비교하며 어떤 관계가 있는지 알아야 한다. 이렇게 스티커를 열로 분해하는 아이디어가 중요한것 같다. 먼저 스티커는 2Xn 이고 N번째 열이 표와 같은 상태일때 N-1번째에 올 수 있는 상태는 다음과 같다.(같은 행에 OO가 올 수 없음.)

점화식을 세우기 위해서 배열 d를 정의한다. 

d[N][k] : 스티커가 2XN 으로 주어지고 N열이 상태k 일때 얻을 수 있는 최대 점수(k=0, 1, 2)

위 표를 점화식으로 나타내면(위에서부터 차례대로 k=0, 1, 2)

k = 0 : d[N][0] = max(d[N-1][0], d[N-1][1], d[N-1][2])

k = 1 : d[N][1] = max(d[N-1][0], d[N-1][2]) + a[N][0]

k = 2 : d[N][2] = max(d[N-1][0], d[N-1][1]) + a[N][1]

배열 a는 스티커 자체를 저장하는 배열이다. 첫번째 행을 0행으로 약속했다.  다음으로 초기화를 해야한다. N=1일때 N-1이 0이 되므로 N=1일때는 따로 정해주고 반복문은 N=2일때부터 시작하도록 했다. 

처음에 배열 a를 행렬처럼 생각하고 a[행][열] 이런식으로 인덱싱을 했는데 [열][행] 순으로 되어야 한다는 걸 깨달았다. 조금 헷갈리긴 하는데 하나씩 생각해보면 알 수 있는 사실이었다. 

<전체코드> 

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

public class _9465 { 

	static int test_case, n;
	static int[][] a;
	static int[][] d;

	public static void main(String arg[]) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		test_case = Integer.parseInt(br.readLine());

		while (test_case-- > 0) {
			n = Integer.parseInt(br.readLine());
			a = new int[n + 1][2];
			d = new int[n + 1][3];
			for (int i = 0; i < 2; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 1; j <= n; j++) {
					a[j][i] = Integer.parseInt(st.nextToken());
				}
			}

			d[1][0] = 0;          // 초기화
			d[1][1] = a[1][0];
			d[1][2] = a[1][1];

			for (int i = 2; 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];
			}
			int ans = Math.max(d[n][0], Math.max(d[n][1], d[n][2]));
			System.out.println(ans);
		}
	}

}