[LeetCode] 70.Climbing Stairs

https://leetcode.com/problems/climbing-stairs/

Climbing Stairs - LeetCode

 

문제 설명

당신은 계단을 오르고 있습니다. 정상에 도달하려면 n 단계가 필요합니다.
매번 1 또는 2개의 계단을 오를 수 있습니다. 얼마나 많은 유일한 방법으로 계단을 오를 수 있습니까?

 

풀이

• 예를들어 4칸의 계단으로 올라오는 경우
• 정상에 올라 오기전에 밟을 수 있는 계단의 수는 1개 또는 2개이다
• 1개의 계단이 남았다면 지금까지 3칸의 계단을 올라온 것이고
  2개의 계단이 남았다면 지금까지 2칸의 계단을 올라온 것이다
• 다시 3칸의 계단이 정상이라 가정하고 정상에 올라 오기전에 밟을 수 있는 계단의 수는 1개 또는 2개이다
• 1개의 계단이 남았다면 지금까지 2칸의 계단을 올라온 것이고
  2개의 계단이 남았다면 지금까지 1칸의 계단을 올라온 것이다
• 이것을 그림으로 나타내면

 

풀이 코드

class Solution {
    public int climbStairs(int n) {
        int result = 1;
        int prev = 1;
        int pprev = 0;
        for(int i = 1; i < n; i++){
            pprev = prev;
            prev = result;
            result = pprev + prev;
        }
        
        return result;
    }
}