문제
어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다. 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다.
그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.
오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다. VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오.
예를 들어서, 그림과 같이 좌석이 9개이고, 4번 좌석과 7번 좌석이 VIP석인 경우에 <123456789>는 물론 가능한 배치이다. 또한 <213465789> 와 <132465798> 도 가능한 배치이다. 그러나 <312456789> 와 <123546789> 는 허용되지 않는 배치 방법이다.
풀이
- dp[i] = i개의 좌석에 앉을 수 있는 경우의 수
- 점화식 구하기
dp[i] = dp[i-1] + dp[i-2] - 초기값 설정
dp[0] = 1
dp[1] = 1
이 문제를 유심히 들여다 보면 좌석 선택의 문제를 피보나치 수열로 구할 수 있다는 사실을 알 수 있다.
좌석은 왼쪽 오른쪽 좌석으로 옮길 수 있다는 조건에서 알 수 있듯이 제일 오른쪽 좌석은 자기 자리에 앉거나 왼쪽 좌석에 앉는 경우 밖에 없고
dp[1] -> 1
dp[2] -> 12 | 21
dp[3] -> 132 | 123, 213
dp[4] -> 1243, 2143 | 1324, 1234, 2134
dp[3]을 보면 제일 마지막에 3을 두는 방법, 왼쪽에 3을 두는 방법 두가지로 나뉜다는 것을 알 수 있다.
위의 예로 알 수 있듯이 제일 마지막에 현재 수를 두는 방법은 현재 인덱스가 i라고 했을 때 i-1에 있는 경우의 수와 같고
마지막 수를 왼쪽으로 옮기는 경우의 수는 i-2의 경우의 수와 같다. 따라서 dp[i] = dp[i-2] + dp[i-1]이라는 점화식을 얻을 수 있다.
그리고 문제에서 주어진 vip석을 제외하고 경우의 수를 구해야 하므로 vip석과 vip석 사이에 존재하는 좌석의 갯수의 경우의수 그러니까 dp테이블에 vip석 사이를 조회해주면 해당 가지수를 각각 구해줄 수 있고 이를 서로 곱하면 총 가짓수를 구할 수 있다.
N = int(input())
M = int(input())
vip_sheats =[int(input()) for _ in range(M)]
dp =[0]* (N+1)
dp[0] = 1
dp[1] = 1
for i in range(2, N+1):
dp[i] = dp[i-1] + dp[i-2]
idx_diff= 0
answer = 1
for vip_sheat in vip_sheats:
answer *= dp[vip_sheat - 1 - idx_diff]
idx_diff = vip_sheat
answer *= dp[N - idx_diff]
print(answer)
피드백
간단한 나열을 통해서 경우의 수를 구하는게 피보나치 수열이라는 사실은 알아냈으나 설명하는데까지는 오래 걸렸다.
알고리즘을 푸는데 코딩테스트에 통과하기 위해 풀다보니 지루하고 어려운 과정이라는 생각이 들었었는데 최근에는 원리가 궁금하고 문제를 만나도 어떤 방식으로 풀어볼까 하는 정복하는 재미가 슬슬 붙기 시작했다.
