계단 오르기, 돌다리 건너기

DP : 1차원 배열인 다이나믹 테이블을 이용해서 점화식 형태로 나오는 문제의 값을 구한다

 

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

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

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

 

계단을 오르는 방법을 저장하면서 푸는 문제

1번 계단 1가지, 2번 계단 2가지, 3번 계단 3가지... d[n] = d[n-1] + d[n-2] 형태

 

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 T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        dy = new int[n+1];
        System.out.println(T.Solution(n));

    }
}

 

돌다리 건너기

 

개울은 N개의 돌로 다리를 만들어 놓았습니다.

돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다.

개울을 건너는 방법은 몇 가지?

 

위의 계단 오르기와 비슷하지만 다리 끝에 도착하고 나서 1칸을 더 가야 건넘, 돌다리가 7개면 8번까지 가야 건너지는 것

 

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+1; i++) dy[i] = dy[i-2] + dy[i-1];
        return dy[n+1];
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        dy = new int[n+2];
        System.out.println(T.Solution(n));

    }
}