[JAVA] 2579번 계단 오르기

문제링크

2579번: 계단 오르기

문제해석

 해당 문제는 동적 프로그래밍의 기초문제라고 볼 수 있습니다. 처음에 문제를 접근할 때는 완전탐색으로 문제를 풀이하려고 하였습니다. 그래서 식을 나열하여 규칙을 찾아내려고 하였으나 상당한 어려움에 직면하게 되었습니다. 인터넷을 조사하던 끝에 DP문제임을 알게되었고, DP를 기반으로 기본항을 찾아내는 모습을 찾을 수 있었습니다.

 

1. 마지막 계단을 N번째 계단이라고 가정하였을 시, N-2 + N번째 계단을 밟는 경우

2. 마지막 계단을 N번째 계단이라고 가정하였을 시, N-3 + N-1 + N번째 계단을 밟는 경우

 

직접 만든 그림

해당 식을 이해하는 과정에서 처음에는 헷갈렸습니다. N-3번째 + N-2번째 + N번째도 되는거 아닌가? 라는 고민을 하였지만 파란색과 같은 N-2번째 + N번째임을 알게되고..  (바보!) 다음과 같이 두가지 경우로 추려낼 수 있었습니다.

이를 구현하기 위해 점수를 저장하는 stair[], 각 계단을 밟았을 때의 최대값을 저장할 수 있는 dp[]을 구현하였습니다.

문제코드

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

public class Main {

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

        int[] stair = new int[num];
        int[] dp = new int[num];

        for (int i = 0; i < num; i++) {
            int now = Integer.parseInt(br.readLine());
            stair[i] = now;
        }

        if (num == 1) {
            System.out.print(stair[0]);
        } else if (num == 2) {
            System.out.print(Math.max(stair[1], stair[0] + stair[1]));
        } else {
            dp[0] = stair[0];
            dp[1] = Math.max(stair[1], stair[0] + stair[1]);
            dp[2] = Math.max(stair[0] + stair[2], stair[1] + stair[2]);

            for (int i = 3; i < num; i++) {
                dp[i] = Math.max(dp[i - 2] + stair[i], dp[i - 3] + stair[i - 1] + stair[i]);
            }

            System.out.print(dp[num - 1]);
        }
    }
}

 

※ 처음에 런타임 에러 (ArrayIndexOutOfBounds)를 겪게 되었는데, 그 이유가 num == 1, num == 2일 때를 if문으로 묶어주지 않았기 때문에 발생했었습니다. 예를들어 num = 1로 들어왔는데 dp[2]를 구하고자 한다면 에러가 발생할 수 밖에 없기 때문입니다. DP와 예외처리를 생각해볼 수있는 좋은 문제였다고 생각합니다.