[LeetCode/JAVA] 70. Climbing Stairs

https://github.com/ROUTINE-STUDY/Algorithm

ROUTINE-STUDY/Algorithm

알고리즘 스터디를 진행하고 있습니다.
초보들로 구성되어있으며, 열심히 풀어보고 풀이 방식을 공유하고 피드백을 해주는 스터디입니다.
문의는 댓글 혹은 GitHub 주소를 참고해주세요.

---

문제 출처 : https://leetcode.com/problems/climbing-stairs/

Climbing Stairs - LeetCode

문제 설명

출처 : LeetCode

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

풀이 방법

패턴을 발견하여 풀이하였습니다.
n이 3 이하라면 n을 return 

n이 4 라면,  2의 모든 경우의 수 + 3의 모든 경우의 수
4(n) : 2 + 3 = 5
5(n) : 3 + 5 = 8
...

내 코드(JAVA)

 

// 1 2 3 = 1 2 3 으로 고정값
// 4 = 2의 경우의 수 + 3의 경우의 수
// 5 = 3의 경우의 수 + 4의 경우의 수
// 위 패턴을 발견
public int climbStairs(int n) {
    if(n<=3) return n;
    int[] arr = new int[n];

    arr[0] = 1;
    arr[1] = 2;
    arr[2] = 3;

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

    return arr[n-1];
}

다른 사람 코드

 

public int climbStairs(int n) {
    // base cases
    if(n <= 0) return 0;
    if(n == 1) return 1;
    if(n == 2) return 2;
    
    int one_step_before = 2;
    int two_steps_before = 1;
    int all_ways = 0;
    
    for(int i=2; i<n; i++){
    	all_ways = one_step_before + two_steps_before;
    	two_steps_before = one_step_before;
        one_step_before = all_ways;
    }
    return all_ways;
}

 

피보나치 수열을 활용한 방법

패턴을 파악하여 풀이했지만 그 풀이 내용이 수학적으로 피보나치의 수라는 개념이었습니다.

배열을 생성하지 않고 변수들로만 충분히 구현할 수 있네요.