[LeetCode] 70. Climbing Stairs

[문제 링크]

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

 

[문제]

당신은 계단을 오르고 있습니다. 정상에 도달하려면 n개의 계단을 올라야 합니다. 한 번에 1칸 또는 2칸씩만 이동할 수 있습니다.

정상에 도달하는 방법의 수를 반환하세요.

[풀이 과정]

어떻게 풀어야 하는지 감이 오질 않아 그냥 하나하나 단순하게 구해봤는데 점화식을 찾게 되었습니다.

 

위 점화식을 토대로 구현을 했습니다.

처음에 위 점화식처럼 구현을 했는데 시간 초과가 떠서 생각을 해보니

했던 연산을 계속 하고 있는게 생각이나 계산을 하고 memo라는 배열에 값을 저장하고

이미 계산한 구간이면 값을 바로 memo에서 찾아 return하는 방식으로 구현했습니다.

[코드]

class Solution {
    // 중복 연산을 피하기 위해 결과 저장
    int[] memo;
    public int climbStairs(int n) {

        memo = new int[n+1];
        return answer(n);
    }

    public int answer(int x) {
            if(x == 1) {
                return 1;
            }

            if(x == 2) {
                return 2;
            }

            // 이미 계산했으면 중복 계산하지 않는다
            if(memo[x] != 0) {
                return memo[x];
            }

            // 구했던 점화식
            // 계산하고 memo에 저장
            memo[x] = answer(x-1) + answer(x-2);

            return memo[x];
        }
}

[회고]

이렇게 점화식을 생각만 해내면 쉬운데 점화식을 생각하는 과정이 어려운 것 같습니다.

 

 

 

 

질문과 피드백은 언제나 환영입니다.

감사합니다.