LeetCode: 70번 (Climbing Stairs) [JAVA]

문제 링크

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

Climbing Stairs - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 주어진 길이 n만큼의 누적 값 저장 배열을 생성
2. 배열의 첫 번째 위치에 1, 두 번째 위치에 2를 저장 (만약 n값이 1, 2라면 해당 값을 그대로 반환)
3. 이후 반복문을 통해 점화식 (a[n] = a[n-1] + a[n-2])를 바탕으로 배열을 초기화
4. 배열의 마지막 요소 값을 반환

 문제 자체가 단순한 점화식 해결의 문제이다. 계단을 올라가는 방법이 한 번에 한 개 혹은 두 개의 계단을 오르는 것이기 때문에, 현재 위치의 계단을 오르는 방법의 개수는 (현재 - 1) 계단에서의 가짓수와 (현재 - 2) 계단에서의 가짓수를 더하면 된다.

 주어진 n만큼의 누적값 저장 배열을 초기화한 후, 배열 첫 번째와 두 번째 요소를 1과 2로 저장한다. 만약 n의 값이 1 혹은 2라면 해당 값을 그대로 반환하면 된다. 그리고 반복문을 통해 앞선 점화식 (a[n] = a[n-1] + a[n-2])을 통해 배열을 채워나가며, 배열의 마지막 요소를 답으로 반환하면 된다.

 

class Solution {
    public int climbStairs(int n) {
        if (n == 1) {//계단 한 개
            return 1;
        } else if (n == 2) {//계단 두 개
            return 2;
        }

        int[] acc = new int[n];//누적값 배열
        acc[0] = 1;
        acc[1] = 2;

        for (int i = 2; i < n; i++) {//점화식
            acc[i] = acc[i - 1] + acc[i - 2];
        }

        return acc[n - 1];
    }
}

결과