계단 오르기 (bottom up)

문제

철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 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로 풀면 성능면에서 훨씬 빠르고 메모리 낭비도 적은 장점이 있다!

좋은 웹페이지 즐겨찾기