1063: 계단 오르기

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.tistory.com/49

 

---

 

cjw.git@gmail.com