소소한 개발일지

문제

당신은 계단을 오르고 있습니다. 정상까지 n개의 계단을 올라가야 합니다.

한 번 오를 때 1개나 2개의 계단을 올라갈 수 있습니다.

몇 개의 중복되지 않은 방법으로 정상에 올라갈 수 있을까요?

예시

Input : n = 2

Output : 2

1. 1계단 + 1계단

2. 2계단

Input : n = 3

Output : 3

1. 1계단 + 1계단 + 1계단

2. 1계단 + 2계단

3. 2계단 + 1계단

풀이 : DP

문제를 딱 보자마자 "아 이건 규칙이 있다!" 라고 생각했습니다.

쉽게 떠올릴 수 있는 피보나치 문제랑 비슷하다고 느꼈고 빠르게 풀었습니다.

1개의 계단일 경우는 1가지 방법 (1)

2개의 계단일 경우는 2가지 방법 (1 + 1, 2)

3개의 계단일 경우는 3가지 방법 (1 + 2 / 1 + 1 + 1, 2 + 1)

4개의 계단일 경우는 4가지 방법 (1 + 1 + 2, 2 + 2 / 1 + 2 + 1, 1 + 1 + 1, 2 + 1 + 1)

계속 이어가다 보면 n - 2의 가짓수와 n - 1의 가짓수를 더하면 계단이 n개일 때의 방법의 갯수를 알 수 있습니다.

$$ n = (n-1) + (n-2) $$

코드는 아래와 같습니다.

class Solution {
    public int climbStairs(int n) {
        if (n == 1)
            return 1;
        
        int[] ways = new int[n + 1];

        ways[0] = ways[1] = 1;

        for (int i = 2; i <= n; i++) {
            ways[i] = ways[i - 1] + ways[i - 2];
        }

        return ways[n];
    }
}

DP문제를 처음 접하기에 좋은 문제 같습니다.