[LeetCode] Climbing Stairs

Climbing Stairs

처음으로 직접 맞힌 동적 프로그래밍 문제...!!!!!!!😭😂

class Solution {
    public int climbStairs(int n) {
        int [] counts = new int[n+1];

        counts[1] = 1;
        if (n > 1) counts[2] = 2;

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

        return counts[n];
    }
}

풀이 과정

• 처음에는 아래처럼 막연하게 모든 경우의 수를 다 나열해보았다.

1 -> 1
2 -> 2
3 -> 1+1+1 / 1+2 / 2+1
4 -> 1+1+1+1 / 1+2+1 / 1+1+2 / 2+1+1 / 2+2
...

• 그리고 나열한 것들을 뚫어지게 쳐다봤다..^-^.. 1+1+..+1 제외하면 바로 전이랑 관련이 있나 생각해봤다. (답은 아니지만 암튼 그렇게도 생각해봤다.)
• 내가 나열한 목록은 순서 없이 마구잡이로 나열된 것이라는 생각이 들었다. 그럼 어떻게 나열할까.. 하다가 걷는 단계(?)가 있다는 게 떠올랐다.
• 그러면 처음에 1번 또는 2번 움직이고 그 다음 단계에서 또 1번 또는 2번 움직이고... 라는 아이디어까지 도달했다.
• 이걸 트리로 한 번 그려서 또 쳐다보았다. 그러면 처음 단계에서 1 또는 2 고르고 그 다음에 또 1 또는 2 고르고... 뭔가 중복되는 값이 존재하는 것 같긴 한데 아직까지는 마땅한 규칙을 찾지 못했다.
• 그러다가 문득 처음 단계에서 1을 고르면 나머지는 n - 1일 때의 경우들에 1을 더하는 것, 2를 고르면 n - 2일 때의 경우들에 2를 더하는 것이랑 같다는 걸 깨달았다!!
• 그러면 기본값은 n = 1일 때에는 1, n = 2일 때에는 2이고 그 이후부터는 바텀업 방식으로 계산하면 되는구나!
• 피보나치 수열 계산이랑 굉장히 비슷한 문제인 듯 하다. 엄청 쉬운 문제인 것 같긴 하지만... 동적 프로그래밍 개념이 많이 낯선 만큼 쉬운 문제도 꼼꼼하게 생각한 과정을 기록해놔야 할 것 같아서 일단 자세히 써봤다. 나중에는 이걸 보고 '뭐 이런 걸 이렇게 자세히 써놨대?!'라고 놀라는 날이 오기를..😅