문제

BOJ 9465: 스티커 https://www.acmicpc.net/problem/9465

풀이

조건

• 스티커는 2행 n열로 배치되어 있다.
• 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다.
  • 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.
• 점수의 합이 최대가 되게 스티커를 떼어내려고 한다.
• 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

풀이 순서

• 시간복잡도를 고려하면 DP를 사용해야한다.
• i번째 열의 0번째 행에 붙어있는 스티커를 선택하려면 i-1번째 열의 1번째 행에 붙어있는 스티커를 선택했어야 한다.
• i번째 열의 1번째 행에 붙어있는 스티커를 선택하려면 i-1번째 열의 0번째 행에 붙어있는 스티커를 선택했어야 한다.
• i번째 열의 스티커를 떼지 않으면 i+1열의 스티커는 0번째, 1번째 행에 붙어있는 스티커 둘 중 하나를 뗄 수 있다.

코드

Java

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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// 테스트 케이스 수
		int T = Integer.parseInt(br.readLine());
		
		for(int tc=0; tc<T; tc++) {
			// 카드 열 수
			int N = Integer.parseInt(br.readLine());
			// 카드 점수 입력
			int[][] cards = new int[2][N + 1];
			for(int i=0; i<2; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				for(int j=1; j<=N; j++) {
					cards[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			int[][] dp = new int[2][N + 1];
			// 1번째는 1번째 열 값으로 초기화
			dp[0][1] = cards[0][1];
			dp[1][1] = cards[1][1];
			// N 번째 열 까지 최대 점수를 DP로 구하기
			for(int i=2; i<=N; i++) {
				dp[0][i] = Math.max(cards[0][i] + dp[1][i-1], Math.max(dp[0][i-1], dp[1][i-1]));
				dp[1][i] = Math.max(cards[1][i] + dp[0][i-1], Math.max(dp[0][i-1], dp[1][i-1]));
			}
			// N열에 기록된 점수 중 큰 값 출력
			System.out.println(Math.max(dp[0][N], dp[1][N]));
		}
	}

}

정리

• 1번 테스트케이스에서 예외케이스를 알려줘서 쉽게 풀 수 있었다.