알고리즘/koreatech
1063: 계단 오르기
cjw.git
2020. 12. 11. 15:00
Link : judge.koreatech.ac.kr/problem.php?id=1063
1. 문제
- 평소 운동이 부족하다고 생각한 유정이는 계단 오르기 운동을 하려고 결정 했습니다. 키가 작고 다리가 짧아서 한번에 여러 계단을 오를 수 없었고, 몇 번의 테스트로 한번에 두칸이 안정적으로 오를 수 있는 최대 칸 수 라는걸 깨달았습니다.
운동을 언제까지 할지 결정을 할 필요가 있던 유정이는 매번 서로 다른 방식으로 계단을 오르고, 더이상 새로운 방법으로 계단을 오를 수 없을 때 까지 운동을 하기로 결정을 했습니다.
만약 계단이 5칸 이라면 유정이가 오를 수 있는 방법은
1) 1 - 1 - 1 - 1 - 1
2) 1 - 2 - 1 - 1
3) 1 - 2 - 2
4) 1 - 1 - 2 - 1
5) 1 - 1 - 1 - 2
6) 2 - 1 - 1 - 1
7) 2 - 2 - 1
8) 2 - 1 - 2
으로 총 8가지 방법으로 오를 수 있습니다.
유정이를 위해 오를 수 있는 총 가짓수를 구해주는 프로그램을 만들 어 주세요.
2. 문제의 조건
- 1 <= T <= 25
- 1 <= N <= 25
더보기
3. 문제 접근
- 시간 복잡도
사실상 계산 양이 25 * 25이기 때문에 시간복잡도는 크게 상관 없는 것 같습니다.
- 아이디어
전형적인 DP문제입니다.
유정이는 1칸아니면 2칸밖에 오를 수 없습니다.
이 때 유정이가 1칸을 오르는 경우의 수는
1. (한칸을 오른다) - 1가지 입니다.
유정이가 2칸을 오르는 경우의 수는
2. (두칸을 오른다) - 1가지 입니다.
※ 한칸씩 두 번 오르는 행위는 1 조건과 같으므로 쓰면 안됩니다.
즉 dp[i-1] + dp[i-2]의 점화식이 주어집니다.
4. 풀이 방법
- 1칸을 오를 수 있는 경우의 수는 1가지입니다.
- 2칸을 오를 수 있는 경우의 수는 2가지입니다.
- n>2, n칸을 오를 수 있는 경우의 수는 dp[i-1] + dp[i-2]가지입니다.
5. 소스코드
cjw.git@gmail.com