[BOJ] 백준 2302번 : 극장 좌석 (JAVA)

문제

어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 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)

 

 

풀이

다이나믹 프로그래밍으로 해결할 수 있는 문제였습니다.

 

처음에는 Top-down 방식으로 시도하였으나, 중복되는 부분을 해결하기 만만치 않아서 Bottom-up 방식으로 바꿨고, 규칙성을 통하여 풀었습니다.

 

먼저, VIP 좌석이 없다고 가정하고, N이 1일 때부터 나열을 해 보겠습니다.

 

N = 1일 때는 방법의 가짓수는 1가지 입니다.

 

N = 2일 때는, "1 2" 또는 "2 1"이 가능하므로 2가지 입니다.

 

N = 3일 때는, "1 2 3" or "2 1 3" or "1 3 2" 이 가능하므로 3가지 입니다.

 

N = 4일 때는, "1 2 3 4" or "2 1 3 4" or "1 3 2 4" or "1 2 4 3" or "2 1 4 3" 이므로 5가지 입니다.

 

 

여기서 dp[N] = dp[N - 2] + dp[N - 1]라는 점화식을 도출해낼 수 있고, 이것은 다름아닌 피보나치 수열의 점화식과 동일합니다.

 

중요한 점화식을 알아냈고, 이제 VIP 좌석을 놓는 경우를 결합하여 생각해야 합니다.

VIP 좌석에 경우, 좌우로 이동이 불가능하므로 딱 그 자리에만 놓아야 합니다. 따라서, VIP 좌석을 제외한 좌석들의 경우의 수를 서로 곱하면 됩니다.

 

위 내용은 그림을 통하여 자세히 설명해 보겠습니다.

 

 

 

 

 

문제의 예시를 그림으로 표현하였습니다. 우리는 A 구간에서 좌석을 앉을 수 있는 경우의 수, B 구간에서 좌석을 앉을 수 있는 경우의 수, C 구간에서 좌석을 앉을 수 있는 경우의 수를 서로 곱하면 됩니다. A, B, C는 같은 시간에 일어나는 사건이기 때문입니다.

 

자세한 코드는 아래를 참고하시길 바랍니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.