Dynamic Programing 다이나믹 프로그래밍

알아보기

큰 문제를 직관적으로 이해할 수 있는 작은 문제로 바꾸어서 소형화시킴.
작은 문제의 답을 메모이제이션, 그렇게 점점 큰 문제로 확장시켜 나간다.

이렇게 큰 문제를

잘게 쪼개어 하나씩 해결해나간다.

사용 예시

예를 들어 계단오르기 문제가 그렇다.

계단을 오를때 한번에 한 계단 또는 두 계단씩 올라갈 수 있을 때, 총 7 계단을 올라간다면 

그 방법의 수를 구해보자.

차근차근 처음부터 알 수 있는 것부터 따져보자.

 

먼저 첫번째 계단을 올라가는 방법은 한가지다.
두번째 계단을 올라가는 방법은 한칸+한칸, 두칸으로  두가지다.

세번째 계단을 올라가는 방법은,
두번째 계단에서 올라갈때와 첫번째 계단에서 올라갈때 경우로 나눠진다.
첫번째 계단으로 가는 방법은 한가지였고, 두번째 계단으로 가는 방법은 두가지였으므로,
세번째 계단으로 가는 방법은 세가지이다.

그렇다면, n 번째 계단으로 가는 방법은 n-1번째 계단에서 한칸 오르는 경우 + n-2번째 계단에서 두칸 오르는 경우 이므로

n-1번째 계단으로 가는 경우의 수 + n-2번째 계단으로 가는 경우의 수를 합한 것이다.

우리가 원하는 7번째 계단으로 가는 방법의 수를 도출 할 수 있다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[]dp = new int[n+1];

        // 직관적으로 알 수 있음
        dp[1] = 1;
        dp[2] = 2;

        for(int i=3; i<=n; i++){
            dp[i] = dp[i-2]+dp[i-1];
        }
        System.out.println(dp[n]);

    }
}