[백준] 2302 - 극장 좌석

1. 문제

2302번: 극장 좌석

2. 개요

1번부터 N번까지의 번호가 쓰여진 한 줄로 된 좌석이 있는 극장이 있다.

일반 입장객은 자신의 번호가 쓰여진 좌석에 앉아야 하는데, 자신의 바로 왼쪽이나 오른쪽 좌석에도 앉을 수 있다.

vip 입장객은 자신의 번호의 좌석에만 앉을 수 있다.

이 때, 좌석을 채울 수 있는 경우의 수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

vip의 좌석은 항상 같은 방식으로 채워진다.

즉, vip좌석 사이사이의 일반 좌석 그룹들의 경우의 수를 곱한 값이 답이 된다.

일반 좌석 그룹들의 경우의 수는 피보나치 수열의 값을 가진다. 이를 이용해 답을 도출, 출력한다.

3-2. Python

import sys

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
answer = 1
vips = [0]

for i in range(M):
    vips.append(int(sys.stdin.readline()))

vips.append(N+1)

dp = [0 for i in range(N + 1)]
dp[0], dp[1] = 1, 1

for i in range(2, N + 1):
    dp[i] = dp[i-1] + dp[i-2]

for i in range(M + 1):
    answer *= dp[vips[i + 1] - vips[i] - 1]

print(answer)

3-3. C#

namespace boj_2302
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int answer = 1;
            int N = int.Parse(Console.ReadLine());

            List<int> dp = new List<int>() { 1, 1 };

            for (int i = 2; i < N + 1; i++)
            {
                dp.Add(dp[i - 1] + dp[i - 2]);
            }

            int M = int.Parse(Console.ReadLine());

            List<int> vips = new List<int>() { 0 };

            for (int i = 0; i < M; i++)
            {
                vips.Add(int.Parse(Console.ReadLine()));
            }

            vips.Add(N + 1);

            for (int i = 0; i < M + 1; i++)
            {
                answer *= dp[vips[i + 1] - vips[i] - 1];
            }

            Console.WriteLine(answer);
        }
    }
}