[프로그래머스] 계단 오르기 (java, DP)

문제

 

당신은 계단을 오르고 있습니다. 꼭대기에 도달하려면 n 계단을 올라야 합니다.

매번 1계단 또는 2계단을 오를 수 있습니다. 꼭대기에 도달하기 위해 몇 가지 서로 다른 방법이 있는지 계산하세요.

제한 사항

1 <= n <= 45

입출력 예

n	return
2	2
3	3

입출력 예 설명

입출력 예#1
꼭대기에 도달하는 두 가지 방법이 있습니다.

1계단 + 1계단
2계단
입출력 예#2
꼭대기에 도달하는 세 가지 방법이 있습니다.

1계단 + 1계단 + 1계단
1계단 + 2계단
2계단 + 1계단

 

문제 분석

문제 파악

• 한 번에 1~2 계단만 오를 수 있다.
• 꼭대기까지는 n 개의 계단을 올라야 한다.
• 꼭대기에 도달하기 위해 몇 가지 서로 다른 방법은 몇 개인지 구하는 문제

접근 방법

[basecase]

 

[점화식]

일단, 계단이 1개일 때 경우의 수, 2개일 때 경우의 수, 3개일 때 경우의 수, 4개일 때 경우의 수를 구해봤다.

→ 피보나치와 유사하다.

예를 들어 n=4 일때 4번째 계단까지 갈 수 있는 경우의 수는 n=2 일때와 n=3 일때의 경우의 수를 합친 값이다. (그림 참조)

정답 코드

class Solution {
    public int solution(int n) {
        int[] dp = new int[n+1];
        //basecase
        dp[1] = 1;
        dp[2] = 2;
        
        for(int i=3; i<=n; i++) {
            dp[i] = dp[i-2] + dp[i-1];
        }
        
        return dp[n];
    }
}

 

교훈점

계단 오르기 문제는 피보나치 수열과 유사한 구조를 가지고 있다.