LeetCode 70. Climbing Stairs

LeetCode - The World's Leading Online Programming Learning Platform

문제 파악

• n개의 계단이 있음
• 한 번에 1칸 또는 2칸 이동 가능
• n번째 계단에 도달하는 총 경우의 수 구하기

전형적인 dp 문제이다 (키워드 접근. 배우게 된 점에서 추가 정리 예정)

접근 방법

마지막 계단에 갈 수 있는 방법은 결국 두가지 뿐이다.

1. 마지막 계단의 -1번째 계단에서 가는 방법
2. 마지막 계단의 -2번째 계단에서 가는 방법

dp[i] = i번째 계단에 도달하는 방법의 갯수라 할때 아래처럼 base case 를 표현할 수 있다.

dp[i] = dp[i-1] + dp[i-2]

코드 구현

import java.util.Arrays;

class Solution {
    private int[] memo;
    
    public int climbStairs(int n) {
        memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return dp(n);
    }
    
    private int dp(int n) {
        // base case 
        if (n == 0 || n == 1) return 1;
        
        // memoization: 이미 계산했으면 재사용
        if (memo[n] == -1) {
            memo[n] = dp(n - 1) + dp(n - 2);
        }
        return memo[n];
    }
}

배우게 된 점

DP 문제는 애초에 출제 유형이 낮다고하니 여느 문제가 그렇듯 키워드를 보고 DP문제인지 연결하는 연습을 해두면 좋을것 같다. (응용이 되어 나오겠지만) 대표적인 문제 유형은 아래와 같다.

1. 1차원 누적형 : 계단, 피보나치
2. 2차원 격자형 : 최단 경로, Unique Paths
3. 배낭형 : Knapsack

혹은 ‘마지막 행동 기준’을 잘 보거나, 마지막 행동 dp[i]가 ‘전 행동에 의존하는지’ 를 확인해보자.

혹은 완전탐색으로 문제를 해결한 후 최적화 시키는 방향으로 dp를 도입해보면 좋을것 같다.