[Java] 돌다리건너기

문제

 

풀이

철수가 다리를 건너는 모든 경우의 수를 구해야한다. 복잡한 문제다. 큰 문제는 작은 문제로 만들고, 점점 크게 문제를 풀면 된다. 여기서는 동적 계획법을 사용한다.

먼저 첫 번째 돌다리에 오는 경우의 수는 1이다. 

두 번째 돌다리에 오는 경우의 수는 2이다.

조심해야되는 것은 n을 입력받았을 때 n번째 돌다리에 오는 경우의 수를 구하는게 아니다. 개울을 '건너야' 한다. 그러므로 만약 7을 입력받았다면 그 다음 번째를 구해야 답이 나온다.

코드

package 인프런.동적계획법.돌다리건너기;

import java.util.Scanner;

public class Main {

    static int[] dp;
    public int solution(int N) {
        dp[1] = 1;  // 첫 번째 돌다리에 도착하는 경우의 수
        dp[2] = 2;  // 두 번째 돌다리에 도착하는 경우의 수

        for (int i=3; i<=N+1; i++) {    // n번째가 아닌 n+1까지 경우의 수를 구하고 dp[n+1]의 값이 돌다리는 건너는 모든 경우의 수이다.
            dp[i] = dp[i-2] + dp[i-1];
        }

        return dp[N+1];
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        dp = new int[N+2];  // 1은 인덱스이므로 증가시키고 나머지 1은 돌다리를 지난다는 조건이니깐 +1만큼 더 길이를 늘려야한다.
        System.out.println(T.solution(N));
    }
}