문제

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

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

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

코드

public class BottomUp {
    static int[] dy;
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n = in.nextInt();
        dy = new int[n+1];
        int solution = solution(n);
        System.out.println(solution);
    }
    public static 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];
    }
}

설명

동적 프로그래밍(dynamic programing)의 기초 문제라고 한다. 해당 방식으로 fibonacci 문제도 풀수 있으니 참고하자! 동적 프로그래밍의 방법 중 하나로 bottom up의 개념은 가장 작은 단위부터 하나씩 조립해서 올라가는 개념이다. 계단 올라가기의 경우 1번째 계단의 값 1과 2번째 계단의 값 2를 가지고 그 다음 계단들의 값인 3번째부터 n까지의 계단의 값들을 계속해서 배열에 넣고 마지막에 n번째 배열의 값을 반환해준다. dfs로 풀수 있을법한 문제를 dy로 풀면 성능면에서 훨씬 빠르고 메모리 낭비도 적은 장점이 있다!