문제

LeetCode 70-Climbing Stairs
You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

예시

Example 1:

• Input: n = 2
• Output: 2
• Explanation: There are two ways to climb to the top.
  1. 1 step + 1 step
  2. 2 steps

Example 2:

• Input: n = 3
• Output: 3
• Explanation: There are three ways to climb to the top.
  1. 1 step + 1 step + 1 step
  2. 1 step + 2 steps
  3. 2 steps + 1 step

풀이

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }

        int first = 1;
        int second = 2;

        for (int i = 3; i <= n; i++) {
            int thrid = first + second;
            first = second;
            second = thrid;
        }

        return second;
    }
}

1. 계단이 1칸이면 1가지 방법, 2칸이면 2가지 방법(1+1, 2) 밖에 없으므로 n이 2 이하일 때는 그대로 반환한다.
2. first는 1칸일 때의 방법 수, second은 2칸일 때의 방법 수를 의미한다.
3. 계단이 3칸일 때부터 n칸 까지 for문을 반복한다.
4. thrid에 현재 계단의 경우의 수를 저장하고, first, second를 다음 계산을 위해 한 칸씩 앞으로 옮긴다.
5. 반복문이 끝나면 second에는 n칸 계단을 올라가는 총 방법 수가 들어 있다.

회고

피보나치 수열에 관련된 문제들을 몇 개 풀어서 응용해봐야겠다는 생각이 든다.