• 동물원 : 가로로도 세로로도 붙어있지 않다는 말은 상하좌우로 인접하면 안된다는 말이다. 따라서 스티커와 완전히 동일한 문제이다.

---

문제 이해

스티커가 2*N꼴로 존재한다.
이 때 특정 스티커를 사용하면 상하좌우에 존재하는 스티커는 사용할 수 없게 된다. 스티커 한 개 마다 점수가 존재할 때, 가장 높은 점수를 얻을 수 있도록 스티커를 사용하는 경우를 찾는 문제이다.

---

문제 풀이

여기서 상하좌우의 스티커를 사용하지 못한다고 했지만, "오른쪽"을 사용하지 못한다는 조건은 다른 상황과는 약간 다르다.
현재 상황에서 위, 왼쪽, 아래쪽을 사용하지 못한다는 것은 현재까지의 상황으로 계산할 수 있지만 오른쪽의 경우 미래에 사용하지 못하게 될 것이라는 말이기 때문이다.
즉, 현재 스티커를 사용할 때 자신의 왼쪽에 존재하는 스티커나 자신의 위, 아래에 존재하는 스티커는 사용되면 안된다는 조건으로만 문제를 푼다면, 오른쪽을 사용하지 못한다라는 조건 또한 자동으로 처리되게 된다.
따라서, "오른쪽"을 사용하지 못한다는 것을 현재 위치의 "왼쪽" 스티커는 사용되면 안된다 라는 것으로 생각하고 문제를 풀었다.

우리가 arr[K][0] 혹은 arr[K][1] 번째 스티커를 사용할 때, 둘 다 사용할 수는 없다.(위 아래 모두 사용할 수는 없으므로) 따라서, 우리가 생각해야할 경우는 3가지가 될 것이다.

1. arr[K][0] 스티커 사용 ⇒ arr[K-1][0] 스티커를 사용하지 않는 경우

2. arr[K][1] 스티커 사용 ⇒ arr[K-1][1] 스티커를 사용하지 않는 경우

3. arr[K][0], arr[K][1] 스티커 둘 다 사용하지 않음 ⇒ arr[K-1][0], arr[K-1][1] 중 하나를 사용해도 되고, 모두 사용하지 않아도 된다.

이런 조건으로 점화식을 세워 풀면 될 것이다.

---

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N;
	static long[][] DP;
	static int[][] cost;
	
	static void dp() {
		DP[1][0] = cost[1][0];
		DP[1][1] = cost[1][1];
		DP[1][2] = 0;
		
		for(int i =2;i<N+1;i++) {
			DP[i][0] = Math.max(DP[i-1][1],DP[i-1][2]) +cost[i][0];
			DP[i][1] = Math.max(DP[i-1][0], DP[i-1][2]) + cost[i][1];
			DP[i][2] = Math.max(Math.max(DP[i-1][0], DP[i-1][1]),
                                                             DP[i-1][2]);
			// DP[i][0] : cost[i-1][1]을 사용하거나, i-1번째 스티커를 
            //            사용하지 않아야 함
            // DP[i][1] : cost[i-1][0]을 사용하거나, 
            //            i-1번째 스티커를 사용하지 않아야 함
            // DP[i][2] : i-1행에 있는 스티커 중 하나를 사용하거나, 
            //            모두 사용하지 않아도 상관없음
		}
	}
	
	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		int T = sc.nextInt();
		
		for(int t=0;t<T;t++) {
			N = sc.nextInt();
			DP = new long[N+1][3];
			cost = new int[N+1][2];
			
			for(int i =1;i<N+1;i++) {
				cost[i][0] = sc.nextInt();
			}
			for(int i =1;i<N+1;i++) {
				cost[i][1] = sc.nextInt();
			}
			//DP[i][0] : cost[i][0]번째 스티커 사용
			//DP[i][1] : cost[i][1]번째 스티커 사용
			//DP[i][2] : cost[i][0], cost[i][1] 스티커 모두 사용하지 않음
            //           이 경우, i-1번째 열에 있는 스티커 중 어느 것을 
            //           사용해도 문제가 없다.
			
			dp();
			sb.append(Math.max(Math.max(DP[N][0], DP[N][1]), DP[N][2]))
              .append("\n");
		}
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과