[Inflearn] 자바 알고리즘 문제풀이 #10-01 1. 계단오르기 dynamic programming(동적계획법)

설명

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

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

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

입력 

첫째 줄은 계단의 개수인 자연수 N(3≤N≤35)이 주어집니다.

 

출력 

첫 번째 줄에 올라가는 방법의 수를 출력합니다.

 

예시 입력 1 

7

 

예시 출력 1

21

 

 

 

 

내 풀이

 

 

import java.util.Scanner;

public class Main10_1 {
    static int answer=0, n;
    public void DFS(int sum) {
        if(sum==n) answer++;
        else if(sum>n) return;
        else {
            DFS(sum+1);
            DFS(sum+2);
        }
    }

    public static void main(String[] args){
        Main10_1 T = new Main10_1();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int result=0;
        for (int i = 1; i <= 2; i++) {
            T.DFS(i);
            result += answer;
            answer = 0;
        }
        System.out.println(result);
    }
}

동적계획법은 처음 접하는데 DFS로 푸는 건 아닌 것 같다..ㅋㅋㅋㅋ 그래도 풀어냄. 나는 해냄(?)

강의로 모범답안 확인하러 가야지

 

 

 

선생님 풀이

import java.util.Scanner;

public class Main10_1 {
    static int dy[];
    public int Solution(int n) {
        dy[1] = 1; //1번 계단까지 갈 수 있는 방법의 수 : 1
        dy[2] = 2; //1번 계단까지 갈 수 있는 방법의 수 : 1+1, 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){
        Main10_1 T = new Main10_1();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        dy = new int[n+1];
        System.out.println(T.Solution(n));
    }
}

DP : 복잡한 문제를 아주 작은 단위의 동일한 문제로 쪼개 푸는 것을 반복해 최종적으로 전체 문제를 푸는 방법 (bottom-up방식)

 

첫 번째 계단까지 가는 방법의 수 = 1가지

두 번째 계단까지 가는 방법의 수 = 2가지 (1칸+1칸, 2칸)

 

 

세 번째 계단까지 가는 방법의 수 = 3가지 (두 번째 계단에서 +1하는 방법 => 2가지, 첫 번째 계단에서 +2하는 방법 => 1가지)

세 번째 부터 N번째 계단까지의 결과는 피보나치 수열처럼 바로 전 단계의 결과와, 전전 단계 결과를 더해주면 된다.

 

 

따라서 N번째 계단까지 가는 방법의 수는 1 + 2 + 3 + 5 + 8 + 13 + 21 + ... 가 되는 것이다.

 

 

 

결과