정올 Q1848 극장좌석

정올 Q1848 극장좌석

▶ 문제: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1121&sca=3050

▶ 문제 조건

1. 본인으 좌석 좌,우에 앉을 수 있다.

2. 지정석은 본인만 앉아야 한다.

3. 좌석 갯수 N, 1 <= N, N <= 40

4. 고정석 갯수 M, 0<=M, M<=N

3. 좌석, 고정석이 주어질때 가능한 경우의 수를 구하여라.

▶ 예시

▶ 문제 접근 방법(코딩 이전에 생각한 문제 접근방법)

 모든 경우의 수에 접근하는 것이 필요로 한다고 생각한다. DFS와 유사하게 스택을 사용하여 문제를 해결해 보려한다. 

 각 자리에서 가능한 수를 스택에 넣고 빼면서 수행하는 방식으로 접근해 보겠다.

-> 위 접근방법은 옳바르지 않다. 

물론 DFS를 사용해 가능한 가짓수를 돌며서 수행하여도 결과값은 찾을 수 있을 것이다. 하지만 다이나믹 알고리즘을 사용한다면 좀더 편리 하게 답에 도달 할 수 있었다. 문제풀이 만큼 접근방법이 중요한 부분이다.

▶ 문제 풀이

 다이나믹 문제로 접근하여 점화식을 사용하여 문제를 해결할 수 있다. 앞서 풀어본 분할 정복보다는 점화식에 가까운 문제로 판단 된다. 

점화식을 새우는 부분을 알아보자

f(N)은 N가지 좌석이 연속으로 주어졌을시 가능한 가짓수를 뜻한다.

(물론 지정석은 고려하지 않는다.) 

f(1)  = {1}                                                 1가지 

f(2) = {{1,2},{2,1}}                                        2가지

f(3) = {{1,2,3},{1,3,2},{2,1,3}}                             3가지

f(4) = {{1,2,3,4},{1,2,4,3},{1,3,2,4},{2,1,3,4},{2,1,4,3}}    5가지

위 가능한 가짓수의 형태를 보면 서로간의 관계가 있을을 알 수 있다. 

f(N)에서 가능한 가짓수들중 마지막 숫자가 N으로 끝나는 숫자열의 경우 

f(N+1)에서 2가지로 늘어나는 것을 확인할 수 있다.

즉 f(2)의 숫자열중 2로 끝나는 1,2는 f(3)에서 {1,2,3},{1,3,2}로 되지만

1로 끝나는 2,1은 f(3)에서 {2,1,3}만 가능하다.

그러면 마지막 숫자가 자기자신인 가짓수를 확인해면 f(n-1)고 같다는 것을 확인할 수 있다. ex(f(4)중 마지막 숫자가 4인 숫자열의 갯수는 3가지이다.) 이러한 이유는 쉽게 알 수 있다. x2된것중 반은 n-1로 끝나는 숫자일 것이고 나머지는 n으로 끝나는 것일 것이다. 

그러므로 4로 끝나는 숫자열의 갯수는 f(4-1)이다.

따라서 f(n) = f(n-2)X2+f(n-1)-f(n-2)인것을 알 수 있다. 

(f(n-1)-f(n-2)는 곱하지 않고 바로 올라온 가짓수이다.)

식을 정리해 보면 f(n) = f(n-2)+f(n-1)이 된다. 어쩌다 보니 피보나치 수열이 됬다....

문제로 다시 돌아가 보면 지정석 을 제외한 연속된 숫자열의 가짓수를 모두 찾고 그 값을 곱하면 답이 나온다. 

문제의 경우 123/4/56/7/89 이므로 f(3) X f(2) X f(2) = 12이다.