leetcode 70, Climbing Stairs

들어가는 말

백준의 주어진 상자로 새로운 상자 만들기와 비슷한 문제다. 여기서는 계단을 오른다고 나와 있지만, 간단하게 말해서 1과 2로 주어진 n을 만드는 갯수를 구하는 거다.

지금까지 해왔던 대로 DP를 이용해서 풀면 된다.

1과 2로 1을 만드는 경우의 수는 1이다. 1과 2로 2를 만드는 경우의 수는 '1+1', '2'로 2이다. 1과 2로 3을 만드는 경우의 수는? '(1+1)+1', (2)+1', '(1)+2'이렇게 3이다. 4라면 '(1+1+1)+1', '(2+1)+1', '(1+2)+1', '(1+1)+2', '(2)+2'로 5이다.

앞서 봤듯이 1과 2로 만들 수 있는 n의 경우의 수는 n-1의 경우의 수 더하기 n-2의 경우의 수이다.

코드 설명

1. 일단 DP 값을 저장한 저장소로 배열을 설정한다. n의 크기가 45밖에 안 되서 배열로 둬도 괜찮다.
2. NullPointException이 나지 않기 위해서 1과 2는 미리 저장을 해준다.
3. 3부터 n까지 계산을 해줘도 좋고 45까지 계산을 해줘도 좋다. 계산 식은 위의 들어가는 말을 참고한다.
4. DP[n]을 리턴하면 된다.

코드

class Solution {
    public int climbStairs(int n) {
        int[] DP = new int[46];
        
        DP[1] = 1;
        DP[2] = 2;

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

        return DP[n];
    }
}

링크

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