[백준(BOJ)] 2302 극장 좌석 - 스위프트(Swift)

[Silver I] 극장 좌석 - 2302

문제 링크

성능 요약

메모리: 69100 KB, 시간: 8 ms

분류

다이나믹 프로그래밍

제출 일자

2023년 11월 6일 14:17:29

문제 설명

어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다. 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다.

그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.

오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다. VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오.

예를 들어서, 그림과 같이 좌석이 9개이고, 4번 좌석과 7번 좌석이 VIP석인 경우에 <123456789>는 물론 가능한 배치이다. 또한 <213465789> 와 <132465798> 도 가능한 배치이다. 그러나 <312456789> 와 <123546789> 는 허용되지 않는 배치 방법이다.

입력

첫째 줄에는 좌석의 개수 N이 입력된다. N은 1 이상 40 이하이다. 둘째 줄에는 고정석의 개수 M이 입력된다. M은 0 이상 N 이하이다. 다음 M 개의 줄에는 고정석의 번호가 작은 수부터 큰 수의 순서로 한 줄에 하나씩 입력된다.

출력

주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 2³¹-1)

 

풀이

우선 VIP석을 기준으로 좌석을 나눈 다음, 나눠진 좌석의 경우의 수를 생각해보았습니다. 

만약 1 자리이면 1, 2 자리이면 2, 3 자리이면 3, 4자리이면 5가 나타남을 파악하였고, 이를 통해 dp로 문제를 해결하고자 하였습니다.

dp[n] = dp[n-2] + dp[n-1]

 위 식을 통해 좌석에 앉을 수 있는 방법의 가짓수를 알 수 있습니다. 

 

예시를 보면 VIP를 제외한 좌석이 3자리, 2자리, 2자리로 나눠져있습니다.

따라서 (3자리일 때의 경우의 수) * (2자리일 때의 경우의 수) * (2자리일 때의 경우의 수)를 해주게 되면 가능한 모든 좌석의 경우의 수를 알 수 있습니다.

즉, 예시를 기준으로 dp[3] * dp[2] * dp[2]가 위 문제의 정답이 됩니다.

 

다음은 이를 코드로 구현한 결과입니다.

let n = Int(readLine()!)! // 좌석의 총 개수
let m = Int(readLine()!)! // 이미 예약된 좌석의 수
var vipSeats = [Int]()

for _ in 0..<m {
    let reservedSeat = Int(readLine()!)!
    vipSeats.append(reservedSeat)
}

var dp = [Int](repeating: 0, count: n + 1)

dp[0] = 1
dp[1] = 1

if n >= 2 {
    for i in 2...n {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
}

var ans = 1
var prevReservedSeat = 0

for vip in vipSeats {
    let emptySeats = vip - prevReservedSeat - 1
    ans *= dp[emptySeats]
    prevReservedSeat = vip
}

let remainingEmptySeats = n - prevReservedSeat	// 마지막 부분 처리
ans *= dp[remainingEmptySeats]

print(ans)