Informatica Online Judge

  극장 좌석 배치5 [2345 / 0929]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 17   Total Tried : 23


The Champion of this Problem (C++) : gs18052 - ms / 420byte
My Best Submission (C++) : N/A

[JKJeong 2019]

Background

극장에 $n$개의 빈 좌석이 있다.

1명 이상의 관객들이 $n$개의 좌석에 앉을 수 있는 서로 다른 방법을 출력하고 그 수를 구하는 프로그램을 작성하시오.

(단, 각 사람을 서로 구분되지 않으며, 한 명이 좌석에 앉으면 그 왼쪽이나 오른쪽 중 적어도 하나의 의자는 비어있도록 배치하라. 단, 왼쪽 끝의 경우 사람이 앉으면 그 오른쪽 자리는 반드시 비워야 하며, 오른쪽 끝에 앉으면 그 왼쪽에는 아무도 앉을 수 없다. 즉, 가장 끝 바깥쪽은 사람이 앉아 있는 것과 같이 가정한다.)

Input

첫 번째 줄에 $n$이 공백으로 구분되어 입력된다.

[입력값의 정의역]
$1 ≤ n ≤ 20$

Output

한 줄에 하나의 사례를 출력한다.

사람이 앉은 자리는 1, 비어있는 자리는 0으로 표현하여 하나의 수를 만들어서 출력한다.

앉은 형태 하나를 수로 생각할 때 내림차순(큰 수를 먼저)으로 출력한다.

마지막 줄에는 그러한 경우의 수를 출력한다.

IO Example

입력
3

출력
101
100
010
001
4


- 예제에 대한 설명

좌석 3개가 있으며 1명이 앉는 경우와 2명이 앉는 경우에 대해서 생각할 수 있다. 3명은 앉을 수 없으므로 다음과 같이 앉을 수 있는 4가지 방법이 존재한다.

●◯●, ●◯◯, ◯●◯, ◯◯●

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]