문제

• 문제 설명 : https://leetcode.com/problems/climbing-stairs/

제출한 코드

package easy;

public class ClimbingStairs {
    // TimeOut Exception
    /*public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 2;
        } else {
            return climbStairs(n-1) + climbStairs(n-2);
        }
    }*/

    int[] resultArray = new int[46];

    public int climbStairs(int n) {
        if (n <= 0) {
            return 0;
        }
        if (resultArray[n] != 0) {
            return resultArray[n];
        }
        if (n == 1) {
            resultArray[1] = 1;
            return 1;
        } else if (n == 2) {
            resultArray[2] = 2;
            return 2;
        } else {
            resultArray[n] = climbStairs(n-1) + climbStairs(n-2);
            return resultArray[n];
        }
    }
}

잘한점

• 문제 풀이 방식이 바로바로 떠올랐고, 바로바로 풀 수 있었음
• memoization을 사용하는데 어려움이 없었음

개선할 점

• n이 0 이하인 경우는 따로 처리하지 않아도 됐는데, 추가적인 코드를 적었음
• memoization을 통해 속도를 더 올릴 수 있었지만, 처음엔 무작정 제출부터 진행했음

Most Upvote Code

public class Solution {

public int climbStairs(int n) {
    if(n == 0 || n == 1 || n == 2){return n;}
    int[] mem = new int[n];
    mem[0] = 1;
    mem[1] = 2;
    for(int i = 2; i < n; i++){
        mem[i] = mem[i-1] + mem[i-2];
    }
    return mem[n-1];
}

배울 점

• 재귀적인 방법이 아니라, 수학적인 점화식을 통해 문제를 풀었음
• memoization 리스트를 지역변수로 사용 함

Submission Image