알고리즘 & BOJ 2302 극장좌석(C++)

1848 : 극장 좌석

제한시간: 1000 ms    메모리제한: 0 MB
해결횟수: 381 회    시도횟수: 1023 회   

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

 

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

 

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

 

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

 

 

 

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

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

[Copy] 9 2 4 7

[Copy] 12

출처 : KOI 전국 2005 초3

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

/**************************************************************     Problem: 1848     User: a132034     Language: C++     Result: Success     Time:0 ms     Memory:1100 kb ****************************************************************/     #include    <cstdio> #pragma warning(disable : 4996)   int VIP[44]; int D[44][44]; int main() {     int N, M;     scanf("%d%d", &N, &M);     for (int i = 1; i <= M; ++i)     {         int tmp;         scanf("%d", &tmp);         VIP[tmp] = 1;     }       D[1][0] = 0;     D[1][1] = 1;       for (int i = 2; i <= N; ++i)     {         if (VIP[i] == 1 || VIP[i - 1] == 1) D[i][i - 1] = 0;         else D[i][i - 1] = D[i - 1][i - 1];                   D[i][i] = D[i - 1][i - 1] + D[i - 1][i - 2];     }     printf("%d", D[N][N] + D[N][N-1]);     return 0; }

BOJ 링크

다이나믹 프로그래밍. 다이나믹 프로그래밍 위주로 풀어나가니 몇 번 풀어보았던 유형의 문제는 어느정도 점화식이 보이기 시작한다. 

확실히 머리좋은게 제일 좋겠지만... 머리가 좋은게 아니라면 같은 유형을 여러번 풀어보면 못 풀지는 않나보다... 물론 새로운 문제를 보면 또 멘탈이 나가겠지만. 

이번 문제의 점화식은 처음 

D[i]를 i번까지의 길이에서 총 방법의 갯수라고 생각했다. 

그렇게 생각하려다 예전에 풀었던 문제들이 생각났고... 

D[i]일 경우 i길이에서 끝날 수 있는 좌석번호는 분명 i 아니면 i-1일 것이 분명했다. 

9길이의 극장좌석이라면 1 2 3 4 5 6 7 8 9 또는 1 2 3 4 5 6 7 9 8 같은 형식으로 

앞은 상관없이 끝이 9 또는 8로 끝날 것이고 만약 자신이나 이전이 VIP라면 무조건 9로만 끝날 것이다. 

이것을 해결하기 위해 차원을 하나 추가하였다.

D[i][i]와 D[i][j]이다. (사실 D[44][2]로 배열을 잡아도 되나 의식의 흐름대로 코딩하다 보니 [44][44]로 잡았다...) 

D[i][i] 는 i로 끝나는 i길이의 모든 좌석배치방법이다. 

이렇다고 할 때 

D[i][i] = D[i-1][i-1] + D[i-1][i-2]가 된다. 

9길이의 배열에서 마지막에 9가 오기 위해서는 이전 길이의 배열의 끝이 8로 끝나도 되고 7로 끝나도 되기 떄문이다. 

VIP또한 마지막에 자기자신이 오기때문에 동일하다. 

D[i][i-1] = D[i-1][i-1]이 된다. 이는 마지막에 8이 오는 경우인데 8이 오기 위해서는 8인 배열의 끝이 7인 경우의 수(D[i-1][i-2])제외해 주어야 하기 때문이다. 7로 끝나는 경우 9가 올 수 없기 때문이다. 

1 2 3 4 5 6 8 7 처럼 7이 오는 경우에 8을 9번째 자리로 놓으면 9는 현재 8의 위치인 7번째에 놓아야 하기 때문에 이런 경우는 불가능하다. 

VIP인 경우에는 이런 경우가 있을 수 없으므로 당연히 0이 된다.