다이나믹프로그래밍 - 계단오르기

문제

https://www.acmicpc.net/problem/2579

분석/설계

다이나믹 프로그래밍으로 풀어봤습니다.

점화식을 아래와 같이 만들어봤습니다. 

dp[n] = Math.max(dp[n-3] + arr[n-1], dp[n-2]) + arr[n]

dp[1], dp[2], dp[3] 같은 예외 사항들은 직접 식을 정의해주고 처리했습니다.

구현 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();

        int[] arr = new int[301];
        int[] dp = new int[301];
        for (int i = 1; i <= N; i++) {
        	arr[i] = scanner.nextInt();
        }
        	
        dp[1] = arr[1];
        dp[2] = arr[1] + arr[2];
        dp[3] = Math.max(arr[1], arr[2]) + arr[3];

        for (int n = 4; n <= N; n++) {
            dp[n] = Math.max(dp[n - 3] + arr[n - 1], dp[n - 2]) + arr[n];
        }

        System.out.println(dp[N]);
        scanner.close();
    }
}

정리

바텀업이 익숙해서인지 탑다운으로는 풀이를 잘 안하게됩니다.

탑다운으로 푸는 방식들이 많이 있으니 혹시 안풀릴 경우 검색해보시거나 아래 링크를 참고하면 도움이됩니다.

다이나믹은 바텀업의 경우 예시를 들어놓고 점화식으로 정리할경우 매우 빠르게 풀수있습니다.

익숙해지려면 많이 문제 유형을 만나보고 점화식을 정의할수 있게 고민해야 봐야할 것 같습니다.

참고

https://www.acmicpc.net/problem/2579

https://st-lab.tistory.com/132