[알고리즘 문제]계단오르기 - 다이나믹 프로그래밍(Bottom-Up)

▷ 문제

철수는 계단을 오를 때 한번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는

1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2로 5가지이다.

그렇다면 총 N계단일 때 올라갈 수 있는 방법의 수는 몇 가지인가?

* 입력
첫째 줄은 계단의 개수인 자연수 N(3<=N<=35)이 주어집니다.
* 출력
첫 번째 줄에 올라가는 방법의 수를 출력합니다.

▷ 입력 예시

7

▷ 출력 예시

21

▷ 풀이

import java.util.*;

class Main {
    static int[] dy;
    public int solution(int n){
        dy[1] = 1;
        dy[2] = 2;

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

        return dy[n];
    }
    public static void main(String[] args){
        Main main = new Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        kb.close();
        dy = new int[n+1];
        System.out.println(main.solution(n));
    }
}

▷ 메모

• 다이나믹 프로그래밍(동적 계획법)은 일반적으로 바텀업과 탑다운 방식을 사용하여 푼다.
• 바텀업 방식은 주로 반복문, 탑다운 방식은 재귀함수를 사용하여 문제에 접근한다.
• 각 계단에 올라가는 방법의 수를 가지는 배열 dy를 선언하여 바텀업 방식으로 문제를 풀 수 있다.