[LeetCode] 70. Climbing Stairs - Java

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

Climbing Stairs - LeetCode

---

문제

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

 

Constraints:

• 1 <= n <= 45

---

풀이

풀이 과정

n개의 계단을 올라가는데 한 번에 한 계단 또는 두 계단씩만 올라갈 수 있다고 할 때, 마지막 계단에 도달할 수 있는 방법의 총 개수를 구하는 문제이다

먼저 한 개의 계단을 올라가는 방법은 시작점부터 한 개의 계단을 올라오는 한 가지의 방법이 있고,
두 개의 계단을 올라가기 위해서는 한 개씩 두 번 올라오거나, 두 개를 한 번에 올라가는 두 가지의 방법이 있다.

세 개의 계단을 올라가는 경우는 반대로 시작점 부터가 아닌 도착점부터 생각을 한번 해보자
한 번에 한 계단 또는 두 계단씩만 올라갈 수 있으므로 세 번째 계단에 도착하기 위해서는 첫 번째 계단에서 올라오는 경우, 두 번째 계단에서 올라오는 경우 각각 한 가지 씩이 존재한다. 그렇다면 첫 번째 계단에 도착할 수 있는 경우의 수 1과, 두 번째 계단에 도착할 수 있는 경우의 수 2를 더한다면 세 번째 계단에 도달할 수 있는 경우의 수를 구할 수 있게 된다.

이를 다시 정리 해보면, 만약 n번째 계단에 도착하려고 한다면 n-1번째 계단에서 올라오는 경우 한 가지와 n-2번째 계단에서 올라오는 경우 한 가지가 존재하며 각각의 경우의 수의 합이 n번째 계단에 도착할 수 있는 경우의 수가 된다.

즉, F(1) = 1, F(2) = 2의 초기값을 가진 F(n) = F(n-1) + F(n-2) 형태의 피보나치 수열을 구하는 문제이다.

시간복잡도를 줄이기 위하여 이전에 구한 값을 저장하고 이용하는 동적 프로그래밍 방식을 사용한다.

전달받은 n이 1부터 45까지의 정수이므로 길이 45만큼의 배열을 선언한다.

static int[] data = new int[45];

 

n번째 피보나치 수를 구하는 함수를 생성한다.
n이 1 또는 2일 때는 그 값을 그대로 return하며 2보다 큰 경우에는 저장된 값이 있다면 그 값을 return
저장된 값이 없다면 n에 대한 피보나치 함수를 구하는 동시에 값을 배열에 저장한다.
배열이 0번 인덱스부터 시작하므로 n에 대해서 n-1번째 인덱스를 사용한다.

static int fibonacci(int n){
    if(n < 3) return n; // 1과 2일 경우, 그대로 return
    if(data[n-1] != 0) return data[n-1]; // data 배열에서 n-1에 대해 저장된 값이 있으면 그 값을 return
        
    return data[n-1] = (fibonacci(n-1) + fibonacci(n-2)); // data 배열에 저장된 값이 없다면 n번째 피보나치 수를 구하는 동시에 return
}

 

생성한 함수를 호출하여 값을 return 한다.

public int climbStairs(int n) {
    return fibonacci(n); // n번째 피보나치 함수
}

 

최종 코드

class Solution {
    static int[] data = new int[45]; 
    
    public int climbStairs(int n) {
        return fibonacci(n); // n번째 피보나치 함수
    }
    
    static int fibonacci(int n){
        if(n < 3) return n; // 1과 2일 경우, 그대로 return
        if(data[n-1] != 0) return data[n-1]; // data 배열에서 n-1에 대해 저장된 값이 있으면 그 값을 return
        
        return data[n-1] = (fibonacci(n-1) + fibonacci(n-2)); // data 배열에 저장된 값이 없다면 n번째 피보나치 수를 구하는 동시에 return
    }
}

---