[상태 정의를 통한 탐색] 계단 오르기 3 [3121 / 0C31]
Time Limit(Test case) : 3000
(ms)Number of users who solved : 707 Total Tried : 1488
The Champion of this Problem (C++) : gs22032 - ms / 230byte
My Best Submission (C++) : N/A
[koistudy.net (unkonwn)]
Background
OO이와 XX가 계단을 올라가려고 한다.계단은 모두 n칸으로 구성되어 있다.
OO이와 XX는 한 번에 1칸, 2칸을 오를 수 있다.
OO이와 xx가 0번째 칸에서 출발하여 동시에 n번째 칸으로 올라가는 서로 다른 방법의 수를 구하는 프로그램을 작성하시오.
만약 n이 3이면
- (1, 1), (2, 2), (3, 3)
- (1, 1), (3, 3)
- (1, 2), (3, 3)
- (2, 1), (3, 3)
- (2, 2), (3, 3)
로 모두 5가지 경우가 있다.
Input
첫 번째 줄에 계단의 수를 나타내는 정수 n이 입력된다.[입력값의 정의역]
1 ≤ n ≤ 15
Output
계단을 올라가는 서로 다른 경로의 수를 출력한다.IO Example
입력3
출력
5
보충 설명 :
이 문제는 계산문제 중 카운팅 문제입니다.
초기 상태는 OO이와 XX가 0번째 칸에 있는 것이고, 목표 상태는 OO이와 XX가 n번째 칸에 있는 것입니다.
수행 작업은
(1칸 이동, 1칸 이동)
(1칸 이동, 2칸 이동)
(2칸 이동, 1칸 이동)
(2칸 이동, 2칸 이동)
로 총 4가지가 있다.
여기서 구하고자 하는 것은 수행 작업을 통해 초기 상태에서 목표 상태로 가는 경로의 수입니다.
"[상태 정의를 통한 탐색] 계단 오르기 2"과 현재 상태를 표현하는 방법과 수행 작업의 수, 목표 상태의 조건 추가이다.
Prob Analysis : [Problem Statistics] | [Solution]
