[Java] 백준 계단 오르기

1. 문제 분석

DP(Dynamic Programming)문제다. 

각 계단을 걸어갈 때를 생각해보며 점화식을 만들어 보았다.

arr는 각 계단에 존재하는 점수의 집합이다.

 

dp[계단 없음] = arr[0](0이 된다.)

dp[계단 1개] = arr[1]

dp[계단 2개] = arr[1] + arr[2]

 

여기까지는 간단하게 세울 수 있다. 하지만 조건에서 연속된 세 개의 계단은 밟으면 안된다고 한다.

3개일 때 1번째 -> 3번째, 2번째 -> 3번째가 가능하다. 그러므로 dp[계단 3개] = arr[3] +((arr[2] + dp[0]), (dp[1])중 최댓값

dp테이블은 각 계단일때의 최댓값을 저장해둔 상태다. 그러므로 위와 같은 점화식을 얻을 수 있다.

 

4개일 때는 1번째 -> 2번째 -> 4번째,  1번째 -> 3번째 -> 4번째, 2번재 -> 4번째가 가능하다.

하지만 2번째 -> 4번째와 1번째 -> 2번째 -> 4번째 중 당연히 후자가 더 클 것이다.

그러므로 dp[계단 4개] = arr[4] +((arr[3] + dp[1]), (dp[2]))중 최댓값이 된다.

 

이제 반복되는 식이 보인다. dp[계단 n개] = arr[n] +((arr[n-1]  + dp[n-3]), (dp[n-2]))

점화식을 찾았으니 이제 구현을 하자.

2. 구현

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        //BufferedReader 로 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int count = Integer.parseInt(br.readLine());
        //계단 값을 저장
        int[] arr = new int[count + 1];
        //계단을 걸어간 최대값을 저장
        int[] dp = new int[count + 1];

        //계단 값 입력
        for (int i = 1; i <= count; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        //하나도 안감
        dp[0] = 0;
        //1칸
        dp[1] = arr[1];
        //2칸 -> count가 1이면 오류남.
        if(count >= 2){
            dp[2] = arr[1] + arr[2];
        }
        
        //점화식 사용
        for (int i = 3; i <= count; i++) {
            dp[i] = arr[i] + Math.max(arr[i - 1] + dp[i - 3], dp[i - 2]);
        }
        System.out.println(dp[count]);
    }
}

만약 dp[2]를 구하는데 arr의 크기는 1이라고 하면 index오류가 나오니 if문으로 처리했다.

나머지는 위에서 구한 점화식을 적용하여 구했다.

3. 마무리

요즘 알고리즘을 너무 안풀어서 그런지 머리가 굳은 것 같다.

이런 문제도 못풀어서 구글링을 하고있으니... dp는 일단 dp 테이블과 점화식을 생각해보자.