(Java) 백준 2579 - 계단 오르기

이 문제에 DP를 어떻게 적용할건지 고민이 많이 되었다.

지금 나는 DP 문제를 해결하는데 두 가지 큰 어려움이 있다.

 

1. DP를 사용하는것이 옳은지 판단하는것이다.

• 최적 부분 구조 : 문제를 나눌수 있어야 하고 나눈 문제들을 모아서 원래 문제를 해결할 수 있는 경우
• 중복 부분 문제 : 나눈 문제에서 동일한 계산을 계속 해야하는 경우

2. 문재를 읽으면서 점화식을 발견해야 한다.

 

문제가 1번 조건에 맞는지 생각을 한참 해봐야 하고, 점화식을 발견하기 위해 또 조금 고민해야 한다.

다양하게 DP 관련된 문제들을 계속 풀어봐야겠다.

---

최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int answer;
    static int[] score;
    static Integer[] dp;

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

        // 계단이 1개일 경우를 생각해서 n+2 배열 생성
        score = new int[n + 2];
        for (int i = 1; i < n + 1; i++) {
            score[i] = Integer.parseInt(br.readLine());
        }

        answer = 0;
        // topDown 방식 사용시 초기값이 null인게 편하므로
        dp = new Integer[n + 2];

        // topDown 방식 사용시 배열의 초기값이 null이므로 dp[0]에는 0으로 초기화
        dp[0] = 0;
        dp[1] = score[1];
        dp[2] = score[1] + score[2];

        // topDown 방식
        System.out.println(topDown(n));

        // bottomUp 방식
//        bottomUp(n);
//        System.out.println(answer);

    }

    public static void bottomUp(int num) {
        // 점화식 적용
        for (int i = 3; i < num + 1; i++) {
            dp[i] = Math.max(dp[i - 3] + score[i - 1], dp[i - 2]) + score[i];
        }
        answer = dp[num];
    }

    public static int topDown(int num) {
        // 아직 탐색하지 않은 dp일경우 재귀호출
        if(dp[num] == null) {
            dp[num] = Math.max(topDown(num - 3) + score[num - 1], topDown(num - 2)) + score[num];
        }
        return dp[num];
    }
}