백준 9465번 스티커

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

9465번: 스티커

알고리즘 스터디에서 못 풀었던 문제를 dp를 공부하고 나니 이제 풀 수 있었다! 30분 컷!

이제 dp문제를 어떻게 풀어야 할지 감은 잡을 수 있을 것 같다. 

근데 실버 2인데 왜 실버 1이었던 RGB거리보다 어렵지?.

---

스티커를 선택하면 변을 공유하는 다른 스티커들은 사용할 수 없다고 한다. 여기서 생각한 점

1. 왼쪽부터 시작해서 윗줄의 스티커를 선택하면 다음엔 아랫줄의 스티커를 선택하면 되겠다! (번갈아 선택)
2. dp[0][n] = dp[1][n-1] + 아랫줄 스티커 점수 dp[1][n] = dp[0][n-1] + 윗줄 스티커 점수

그러나 테스트 케이스는 260이 답인데 250이 나왔다. 그림으로 생각해보니

내 알고리즘

정답

정답처럼 반드시 위아래 번갈아 선택하는 것은 아니었다. 저렇게 하려면 1칸을 건너뛴 것, 2칸을 건너뛴 것 중 더 값이 큰 것을 dp테이블에 넣어야 했다. 그리하여 완성된 코드.

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

public class bj9465 {
	static int T,N;
	static int [][] sticker;
	static int [][] dp;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for(int t=0;t<T;t++) {
			N = Integer.parseInt(br.readLine());
			sticker = new int[2][N];
			dp = new int[2][N];
			for(int i=0;i<2;i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for(int n=0;n<N;n++) {
					sticker[i][n]= Integer.parseInt(st.nextToken());
				}
			}
			dp[0][0] = sticker[0][0];
			dp[1][0] = sticker[1][0];
			if(N>=2) {
				dp[0][1] = dp[1][0]+sticker[0][1];
				dp[1][1] = dp[0][0]+sticker[1][1];
			}
			for(int n=2;n<N;n++) {
				//두칸 건너뛰는 것과 한칸건너뛰는 것중에 큰값
				dp[0][n] = Math.max(dp[1][n-1]+sticker[0][n], dp[1][n-2]+sticker[0][n]);
				dp[1][n] = Math.max(dp[0][n-1]+sticker[1][n], dp[0][n-2]+sticker[1][n]);
			}
			sb.append(Math.max(dp[0][N-1], dp[1][N-1])).append("\n");
		}
		System.out.println(sb);
	}
}