2002년 가을학기 문제해결기법 - 문제 5

계단 오르기

한국대학교 박 경목 교수는 엘리베이터를 이용하기보다는 계단 오르기를 좋아한다. 그는 계단 오르기가 다른 어떤 운동보다도 건강을 유지하는데 효과적이라고 주장하곤 한다. 오늘도 수업을 마치고 연구실로 향하던 박 교수는 계단을 오르면서 얼마나 다양한 방법으로 계단을 오를 수 있는지 호기심이 생겼다.

연구실로 돌아온 박 교수는 그 동안 아래와 같은 조건을 항상 만족시키면서 계단을 올랐다는 것을 발견하였다.

C1. 계단을 오르다가 내려가지 않는다.

C2. 한 걸음 옮길 때마다 한 계단 혹은 두 계단을 오른다.

그는 연습장에 계단 5개를 그려놓고 계단 오르는 방법을 나열하여 보았다. 한 계단 올라가는 경우는 1, 두 계단을 한꺼번에 올라가는 경우는 2로 나타내기로 하였다. 계단 오르기 방법의 수는 다름 아닌 합이 5이면서 1과 2를 나열하는 방법의 수와 같음을 알았다. 계단이 5개인 경우 계단 오르기 방법의 수는 모두 8임을 찾았다.

1 1 1 1 1

1 1 1 2

1 1 2 1

1 2 1 1

1 2 2

2 1 1 1

2 1 2

2 2 1

계단 오르기 방법의 수가 생각보다는 훨씬 많음을 알고, 손으로 나열하기를 포기하고 프로그램을 작성하여 가능한 방법을 모두 찾기로 결심하였다. 박 교수가 작성하려는 프로그램을 작성하는 것이 문제이다. 즉 계단의 수 n이 입력될 때 계단 오르기 방법의 수와 그 방법을 모두 찾아 사전 순서로 나열하는 것이다.

프로그램 이름과 설명 파일 이름은 각각 stair.xxx, stair.yyy라고 하고 실행 파일 이름은 stair.exe로 한다. 프로그램의 실행 시간은 5초를 초과할 수 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 첫 줄에 계단 수 n이 입력된다. n은 12 이하인 양의 정수이다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 첫째 줄에 계단 오르기 방법의 수를 출력한다. 둘째 줄부터 마지막 줄까지 한줄에 하나씩 계단 오르기 방법을 모두 나열한다. 이때 사전 순서로 나열하며, 출력하는 정수들 사이에 공백을 하나 둔다.

입력과 출력의 예

INPUT.TXT

5

OUTPUT.TXT

8

1 1 1 1 1

1 1 1 2

1 1 2 1

1 2 1 1

1 2 2

2 1 1 1

2 1 2

2 2 1