문제

BOJ 2302: 극장 좌석 https://www.acmicpc.net/problem/2302

풀이

조건

• 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다.
• 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다.
• 그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.

풀이 순서

• 고정석을 기준으로 덩어리를 나눈다.
• 덩어리 크기에 따른 좌석 배치 경우의 수를 구한다.
  • 크기가 1: 1자리
    • 1
  • 크기가 2: 2자리
    • 1, 2, 2, 1
  • 크기가 3: 3자리
    • 1, 2, 3, 2, 1, 3, 1, 3, 2
  • 크기가 4: 5자리
    • 1, 2, 3, 4, 2, 1, 3, 4, 1, 3, 2, 4, 1, 2, 4, 3, 2, 1, 4, 3
  • 크기가 5: 8자리
    • 1, 2, 3, 4, 5, 2, 1, 3, 4, 5 ...
• f(n) = f(n-1) + f(n-2)와 같은 식을 구할 수 있다.
• 덩어리의 크기를 구해 답을 구한다.

코드

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 N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		
        // 고정석 입력받은 후 저장(1번 부터 저장)
		int[] fix = new int[M + 1];
		for (int i=1; i<=M; i++) {
			fix[i] = Integer.parseInt(br.readLine());
		}
		
        // 자리를 옮길 수 있는 사람들의 수에 따라 생기는 경우의 수 저장(DP)
		int[] count = new int[50];
		count[0] = 1;
		count[1] = 1;
		count[2] = 2;
		for(int i=3; i<=N; i++) {
			count[i] = count[i-1] + count[i-2];
		}
		
        // 고정석을 기준으로 나눈 덩어리를 구해 정답 구함
		long answer = 1;
		for(int i=1; i<=M; i++) {
			int fixCnt = fix[i] - fix[i-1] - 1;
			answer *= count[fixCnt];
		}
        // 마지막 덩어리 처리
		answer *= count[N - fix[M]];
		
		System.out.println(answer);
	}

}

정리

• count[0] = 1을 빼먹어서 틀렸었다.