BOJ - 2302번 극장 좌석 문제 (C++) dp를 이용한 풀이 회고

들어가면서..

문제 설명을 처음 읽고, 전체 문제를 작은 단위의 문제로 쪼갠 뒤 그 결과를 조합해서 전체 문제를 해결해야겠다는 느낌은 받을 수 있었으나 아이디어가 명확하게 떠오르지는 않았습니다.

 

https://www.acmicpc.net/problem/2302

2302번: 극장 좌석

그렇게 몇 번 풀이를 미루다가 오늘 이 문제를 다시 풀게 되었습니다.

 

 

다른 방식의 풀이를 보아하니 fibonacci 방식으로 수열이 이어지고, 이를 곱하는 결과로 계산을 한 풀이가 대부분이었는데, 저는 다른 방식으로 접근했기에 이를 정리해보려고 합니다.

---

문제 설명

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

 

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

 

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

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

 

문제 설명 그림

---

나의 접근 방식

저는 전체 문제를 좌석의 길이를 기준으로 작은 문제로 쪼개는 방식을 고려했습니다.

 

 

길이가 1인 좌석의 경우의 수를 활용해 길이가 2인 좌석의 경우의 수를 구하고, 계속해서 이를 확장하는 방식이죠

여기에 더해 자신의 좌석의 바로 양옆 자리까지 앉을 수 있는 경우에서 길이의 마지막 좌석이 자신의 자리를 지키는 경우와 왼편과 자리를 교체하는 경우로 경우의 수를 나눠서 고려했습니다.

 

 

이렇게 생각을 하니 다음과 같은 점화식을 만들 수 있었습니다.

 

n 길이 좌석에서 n번째 자리를 고수 O = n - 1 길이 좌석의 전체 경우의 수 (자리를 고수 O + 자리를 고수 X)

n 길이 좌석에서 n번째 자리를 고수 X = n - 1 길이 좌석에서 n - 1번째 자리를 고수 (그래야 자리 교체가 가능하므로!!)

 

 

말로만 해서는 이해가 잘 안 되니 다시 경우의 수를 직접 나열해서 살펴보면 다음과 같습니다.

// i: (자리 지킴, 벗어남)
1: (1, 0)
-> {1}, {}
2: (1, 1)
-> {1, 2}, {2, 1}
3: (2, 1)
-> {(1, 2, 3), (2, 1, 3)}, {1, 3, 2}
4: (3, 2)
-> {(1, 2, 3, 4), (2, 1, 3, 4), (1, 3, 2, 4)}, {(1, 2, 4, 3), (2, 1, 4, 3)}
... 이런 식으로 쭉 이어짐

 

이렇게 점화식이 구성되는 이유는

• n번째 자리에서 왼편과 바꿀 수 있으려면, 왼편도 자기 자신의 자리에 앉아야만 하기 때문입니다. (이미 n - 1번째가 왼편과 자리를 교체했다면, 자리 교체가 불가능하기 때문)
  • ex) (1, 3, 2) 여기서 4가 새로 추가되는 상황에서 4는 왼편의 2와 자리 교체가 불가능 → (1, 3, 4, 2)가 되어 불가능한 케이스
• 왼편과 교체하는 케이스만 따지면, 다음 길이에 대한 경우에서 오른편과 교체되는 케이스를 다뤄준다.

이 정도가 있을 것 같습니다.

 

 

여기에 추가적으로 고려해야 하는 문제는 바로 VIP로 인한 고정석이 생기는 경우입니다.

 

 

이때에는 고정석으로 인해 고정석과 고정석 오른편 자리가 자신의 자리를 벗어날 수 없게 되어, 이 경우만 고려해 주면 됩니다.

따라서 점화식을 고려한 코드를 위와 같이 작성했습니다.

dp 배열이 의미하는 바

VIP와 VIP의 다음 자리는 자신의 자리를 지키는 케이스만 가능하기 때문에, 위와 같이 작성했습니다.

---

제출한 코드

#include <iostream>

#define MAX 42
#define endl '\n'

using namespace std;

int n, m;

int dp[MAX][2]; // 0: 지킴, 1: 벗어남

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	cin >> m;

	for (int i = 0; i < m; i++) {
		int fixedSeat;
		cin >> fixedSeat;

		dp[fixedSeat][1] = -1;
		dp[fixedSeat + 1][1] = -1;
	}

	dp[1][0] = 1, dp[1][1] = 0;

	for (int i = 2; i <= n; i++) {
		if (dp[i][1] == -1) {
			// VIP or VIP 다음 자리의 경우
			dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
			dp[i][1] = 0;
			continue;
		}

		dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
		dp[i][1] = dp[i - 1][0];
	}

	cout << dp[n][0] + dp[n][1];

	return 0;
}

 

 

배열 길이를 잘못 할당해서 삽질을 조금 했습니다..

여기서 배열의 길이를 41이 아닌 42로 할당하는데, 이는 VIP 다음 자리까지 접근하도록 배열을 만들어줬기 때문입니다. 아마 더 나은 방식으로 코드를 작성할 수 있을 것 같습니다.

 

---

다른 풀이 방식에 대해서

다른 풀이들은 고정석을 기준으로 fibonacci를 적용해 발생하는 케이스들을 곱하는 방식으로 문제를 많이 해결한 것을 확인할 수 있었습니다.

 

 

일단 fibonacci가 되는 이유는

n길이의 배열 경우의 수 = n - 1 길이 배열에 그대로 n을 붙이는 경우의 수 + n - 2 길이 배열에 (n, n-1)을 붙이는 경우의 수

 

이런 식으로도 점화식을 생각해 낼 수 있기 때문입니다. (사실 큰 틀에서 제 점화식과 동일하다고 볼 수 있습니다. 다만, 저는 2차원 배열을 활용했을 뿐)

 

 

어떤 방식이 옳은지에 대한 답은 없다고 생각합니다만, 역시나 dp에서 가장 중요한 것은 점화식을 얼마나 잘 생각해 낼 수 있는지라는 생각을 하게 된 문제인 것 같습니다.