R02703
rook의 경로의 수
실버 I레이팅
의견: 0
설명
길이가 \(n\)인 배열이 있다. 칸에는 왼쪽부터 \(1\)번부터 \(n\)번까지 번호가 붙어 있고, 체스의 룩(rook)이 처음에 \(1\)번 칸에 놓여 있다.
룩은 다음 규칙에 따라 움직인다.
- 룩은 오른쪽으로만 이동할 수 있다.
- 한 번의 이동에서 \(1\)칸 이상, 원하는 만큼 이동할 수 있다.
- 이동 중에 여러 번 멈췄다가 다시 이동할 수 있다.
\(1\)번 칸에서 출발하여 \(n\)번 칸에 도착하는 서로 다른 경로의 개수를 구하여라. 두 경로는 도중에 멈추는 칸의 집합이 다르면 서로 다른 것으로 센다.
노트 — 답이 32비트 정수 범위를 넘을 수 있다.
제약
\(1 < n \le 60\)
입력 형식
첫째 줄에 배열의 길이 \(n\)이 주어진다.
출력 형식
첫째 줄에 \(1\)번 칸에서 \(n\)번 칸까지 이동하는 서로 다른 경로의 개수를 출력한다.
예제 1
입력
3출력
2설명
\(n = 3\)일 때 가능한 경로는 \(1 \to 3\), \(1 \to 2 \to 3\)의 \(2\)가지이다.
예제 2
입력
4출력
4설명
\(n = 4\)일 때 가능한 경로는 \(1 \to 4\), \(1 \to 2 \to 4\), \(1 \to 3 \to 4\), \(1 \to 2 \to 3 \to 4\)의 \(4\)가지이다.
문제 정보
gras 작성
출처 gras(Original)
태그
평가 및 의견
rook의 경로의 수
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
rook의 경로의 수
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기