[Java] 계단 오르는 경우의 수 계산 알고리즘

---

계단 오르기

지현이는 계단을 오를 때 한번에 한 계단 또는 두 계단씩 올라갈 수 있다. 만약 4개의 계단을 올라가려 한다면 그 경우의 수는
1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다
그렇다면 총 N개의 계단이 있을 경우 지현이가 올라갈 수 있는 방법의 수는 몇 가지일까?

DP(Dynamic Programing)

위와 같이 계단의 수가 적은 경우는 직접 세어도 무방하지만 만약 계단의 수가 100개 이렇게 늘어나게 된다면 하나하나 세기에는 어려울 것이다.
이러한 경우 큰 문제를 작은문제로 쪼개어 해결하는 DP를 사용해야 한다.

DP의 경우 작은 문제들의 값을 저장할 DP테이블이 필요하다.
작은 문제들을 해결하고 그 해답을 DP테이블에 저장(Memoization)해 나가면서 큰 문제들을 해결 해 나갈 수 있다.

dp[1] = 1
1개의 계단을 오르는 경우는 1가지 (1)
dp[2] = 2
2개의 계단을 오르는 경우는 2가지 (1+1, 2)
dp[i] = ?
i개의 계단을 오르는 경우는 ?가지

앞의 dp[1]과 dp[2]를 활용하여 3개의 계단을 가는 방법을 구해보자.

3개의 계단을 오르려면

1. 1번쨰 계단에서 두칸 점프해서 올라오는 경우
2. 2번째 계단에서 한칸 점프해서 올라오는 경우

두가지가 존재한다.

따라서 3개의 계단을 오르는 경우의 수는 다음과 같이 구할 수 있다.

dp[3] = dp[1] + dp[2]

4개의 계단을 오르는 경우의 수는

dp[4] = dp[2] + dp[3]

n개의 계단을 오르는 경우의 수는

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

으로 구할 수 있다.

소스코드

public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    
    int dp[] = new int[n+1];
    dp[1] = 1; // 1개의 계단을 오르는 경우의 수
    dp[2] = 2; // 2개의 계단을 오르는 경우의 수

	// n개의 계단을 오르는데 필요한 경우의 수 dp 테이블에 저장하기
    for (int i = 3; i <= n; i++) {
    	dp[i] = dp[i - 2] + dp[i - 1];
    }
    for (int i = 1; i <= n ; i++) {
    	System.out.println(dp[i]);
    }
}
    ```