경기장 일렬 좌석에 앉을 때 사람을 지나치지 않고 전부 앉는 방법의 수

29313번: Стадион (acmicpc.net)

 

일렬로 된 N개의 좌석이 있는데 사람이 양쪽으로 들어가서 좌석에 앉을 수 있다고 할때, 

 

어떤 사람이 이미 앉은 사람을 지나치지 않고 N명이 모두 앉는 방법의 수를 구하는 문제

 

예를 들어 3명이 앉는다고 해보면 이렇게 4가지가 있다

 

 

 

 

N개의 자리가 있을 때

 

_ _ _ _ _ _ ...

 

첫번째 자리에 먼저 앉으면 1 _ _ _ _ _ ...

 

나머지 N-1개의 자리는 고정적으로 2,3,4,5,6,... 으로 1가지 = N-1C0가지 결정된다

 

두번째 자리에 먼저 앉으면 _ 1 _ _ _ _ ....

 

1의 왼쪽 자리 _ 를 N-1명중 1명을 결정시키면 1의 오른쪽은 무조건 자동으로 결정되므로... N-1C1가지

 

왜냐하면 1의 왼쪽에 3을 앉히면 3 1 _ _ _ _ ....

 

1의 오른쪽은 나머지 2,4,5,6,7,..,N 순서대로 앉는 방법밖에 없다

 

세번째 자리에 먼저 앉으면 _ _ 1 _ _ _ ... 

 

1의 왼쪽 자리 _ _ 를 N-1명중 2명을 결정시키면 1의 오른쪽은 나머지가 자동으로 결정되므로 N-1C2가지

 

왜냐하면 1의 왼쪽에 5,4를 앉히면 5 4 1 _ _ _ .....

 

1의 오른쪽은 나머지 2,3,6,7,8,9,...,N이 순서대로 앉아야한다

 

사람끼리는 구별되지 않는다고 가정하는듯?

 

아무튼.... 이를 반복하면

 

_ _ _ _ _ ... 1 _ 에서 1의 왼쪽 자리 N-1명중 N-2명을 결정시키면 1의 오른쪽은 나머지가 자동으로 결정되니 N-1CN-2

 

_ _ _ _ _ ... 1 에서 1의 왼쪽 자리 N-1명중 N-1명을 결정시키면.. N-1CN-1가지

 

그래서 전체 경우의 수는...

 

N-1C0 + N-1C1 + N-1C2 + ... + N-1CN-1 = $2^{N-1}$

 

m = int(input())

mod = 10**9 + 7

print(pow(2,m-1,mod))

 

 

앉게 되는 순서를 기록하면 하나의 수열이 되는데 예를 들어 n = 4이면

 

1 2 3 4

 

4 3 2 1

 

2 1 3 4

3 1 2 4

4 1 2 3

 

4 3 1 2

4 2 1 3

3 2 1 4

 

어떤 지점 Si를 기준으로

 

S1 > S2 > ... > Si < Si+1 < Si+2 < ... < SN의 형태를 띄는 수열인데 이를 바이토닉 수열이라고 부른다

 

감소했다가 증가하거나, 증가하거나 감소하는 수열을 말한다

 

감소하다가 증가하는 길이 N인 바이토닉 수열의 개수가 $2^{N-1}$개임을 알 수 있다