KOI 전국 2005 중1- 자리 배치 > 문제은행 : 정보올림피아드&알고리즘



2098 : 자리 배치

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
30 회   
시도횟수
62 회   

문제

어떤 극장의 자리는 한 줄로 배치되어 있고 자리번호는 왼쪽부터 1에서 N까지 차례대로 매겨져 있다. 이 N개의 자리 중에서 N-1개의 자리는 지정석으로 모두 판매하고, 어떤 한 자리만 자유석으로 비워둔다. 지정석 표를 산 사람들은 아래 규칙에 따라서만 앉을 수 있다.

 

규칙) 사람들은 구입한 지정석 표에 적힌 번호의 자리에 앉든지, 그 자리의 바로 왼쪽이나 오른쪽의 인접한 자리에 앉든지, 또는 자유석에 앉을 수 있다.

 

예를 들어 설명해보자. 4개의 자리가 있는 극장의 경우, 아래 그림1과 같이 1, 2, 4번 자리는 지정석으로 판매되었고, 3번 자리는 자유석(회색으로 표시)으로 지정되었다.

 

 

 

아래 그림에서 ⓘ는 지정석 표의 번호가 i인 사람을 나타낸다. 그림2의 (a), (b), (c), (d)는 위의 규칙을 만족하는 자리배치의 예이다.

 

 

 

다음 4가지 경우는 위의 규칙을 만족하지 않는 자리배치의 예이다.

 

 

 

그림3의 (a)는 4번 좌석표를 받은 사람이 자리에 앉지 않았기 때문에 규칙에 어긋난 자리배치이다. 그림3 (b), (c), (d)의 경우에는 1번 혹은 4번 좌석표를 받은 사람이 원래 자리에서 2칸 이상 떨어진 자리에 앉아서 규칙에 어긋난 경우이다.

 

문제는 전체 자리의 수 N이 주어지고, 자유석 번호 K가 주어져 있을 때, 앞서 말한 규칙을 만족하며 배치할 수 있는 모든 경우의 수를 출력하는 것이다.


입력형식

첫 줄에는 자리의 수 N(3≤N≤40)이, 그 다음 줄에는 자유석의 번호 K(1≤K≤N)가 주어진다.

출력형식

앞서 설명한 규칙을 만족시키며 자리 배치를 할 수 있는 모든 경우의 수를 첫 줄에 출력한다. 이 값은 231-1 이하의 정수이다.

입력 예

4 3

출력 예

8


다이나믹, DP, Fibonacci

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP