LeetCode - 70. Climbing Stairs

leetcode.com/problems/climbing-stairs/

Climbing Stairs - LeetCode

 

 

1스텝또는 2스텝으로만 계단을 올라가는 경우의 수를 구하는 문제. 

고민을 많이 했었는데 결국 풀어내지 못했고 답지를 봤다.

다이나믹 프로그래밍으로 풀어내는 문제였다.

 

Answer1. Top-down approach

만약 주어진 계단의 수가 5개라고 한다면 내가 할 수 있는 경우의 수는

 

1. 1개의 계단을 올라간다.

2. 2개의 계단을 올라간다.

 

둘 중 하나의 경우가 있을 것이다. 

 

그 뒤에 1의 과정을 따르든, 2의 과정을 따르든 남은 계단이 없는게 아니라면 한 개의 계단을 오르던지 두개의 계단을 오르던지 둘 중 하나의 경우를 택하게 될 것이다.

 

이를 토대로 가능성의 tree를 만들고, 모든 가능성을 더해주면 결국 답을 구할 수 있을 것이다. 

 

이때 남은 계단이 없을 경우 할 수 있는 경우의 수는 1이고,

남은 계단이 -1일경우에는 0를 리턴하도록 했다.

 

 

위의 그림과 같이 진행되어서 만약 계단이 5개일 경우 경우의 수는 8이다. 

 

이 알고리즘의 시간 복잡도는 tree의 깊이에 따른 O(2^n)인데, 너무 느려서인지 Leet-code의 테스트를 통과하진 못했다.

 

 

Answer2. Bottom-Up approach

 

위의 코드에서 보면 남은 계단이 2칸이 남았을때, 3칸이 남았을때 등등 많은 경우가 중복해서 발생하는데,

 

이런 자주 나오는 것들을 저장해줌으로써 보다 빠르게 문제를 풀 수 있다.

 

 

 

---

References

www.youtube.com/watch?v=NFJ3m9a1oJQ

leetcode.com/problems/climbing-stairs/solution/