[백준 2302번] 극장좌석 - java

문제 설명

1. 좌석의 개수가 주어진다.

2. 각 좌석은 자신의 양옆으로 이동 가능하며, VIP는 이동이 불가능하다.

3. VIP의 위치가 주어질 때 가능한 좌석의 전체 방법 수를 구하여라

 

풀이 과정

 1. DP를 통해서 풀 수 있다.

 2. 좌석을 한 칸씩 늘려가며 방법을 구해주면 점화식을 세울 수 있다.

먼저 VIP석이 아예 없는 경우를 예를 들어

1칸 -> 1개

2칸 -> (1 2) (2 1) 2개

3칸 -> (1 2 3) (1 3 2) (2 1 3) 3개

4칸 -> (1 2 3 4) (1 3 2 4) (2 1 3 4) / (1 2 4 3) (2 1 4 3) 5개

.... 이렇게 된다.

4번째 칸을 기준으로 구할 때에는 -> 3칸을 구하는 방법 뒤에 4번째 위치 / 3으로 끝나는 좌석을 4와 위치를 바꾸기 이렇게 할 수 있다.

3칸이 3으로 끝나는 경우는 2칸의 뒤에 3이 들어가는 방법이고, 이 때에만 4와 바꿀 수 있다.

즉 4칸의 모든 방법의 개수는 3칸의 모든 방법 개수 + 2칸의 모든 방법 개수이다.

DP[N] = DP[N-1] + dp[N-1] 라는 식이다.

 

그런데 VIP석이 들어간다면 어떻게 될까?

VIP석은 양옆 모두로 좌석을 옮길 수 없다는 것이다.

따라서 만약 4칸이 VIP석이라면, 이전에 구한 마지막이 3으로 끝나는 경우도 바뀌지 않으므로 그대로라는 것이다.

또, VIP의 다음 좌석에서 확인해 보았을 때에도 이전 좌석이 VIP면 그게 뭘로 끝나든 변경 불가하다.

즉 VIP석, VIP의 다음 석의 점화식은

DP[N] = DP[N-1]라는 것이다.

 

 3. 두 가지 점화식을 모두 대입시킨 방안을 사용한다. 이는 HashSet을 사용하여 현재위치가 VIP석이거나 VIP의 다음좌석이면 DP[N] = DP[N-1]으로 저장하는 식으로 쓸 수 있다.

 

 4. VIP석이 아닌경우 DP는 N-2까지 탐색하기 때문에 이를 미리 적어두고 for문에서 잘 처리해야 한다.

 5. 또 VIP석은 딱히 제한사항이 없어, 1번 좌석이나 2번 좌석에도 올 수 있다.

 6. 이를 처리하기 위해 DP[1] = 1(어떤 방법으로든 1임)을 처리해주고 DP[2]일 때 부터 방안을 고려하면 된다.

 7. 이 때 사용할 수 있는 방법이 하나 있는데, DP[2]가 VIP석이면 이는 DP[1]을 그대로 가져올 것이고 DP[2]가 VIP석이 아닌 경우는 2개의 좌석이 생길 것이다.

 8. 그리고 DP[1]은 이미 만들었으므로 DP[2]에서만 사용해줄 DP[0]을 1로 설정해 주면 간단하게 구현 가능하다.

코드