[BOJ] 백준 2579번: 계단 오르기 (JAVA)

 

- 문제 출처 : https://www.acmicpc.net/problem/2579

---

1. 생각

DP 문제를 한번 풀어보고 싶어서 "계단 오르기" 라는 문제를 실버 문제여서 골랐는데,

'연속된 세 개의 계단을 모두 밟아서는 안 된다.'는 조건 때문에 어떻게 해결할지 막막했다.

 

DP 테이블을 일단 만들어보려 했는데, 단순히 이전 계단과, 전전 계단의 dp 배열 값으로는 해결하지 못했다.

2. 난관 & 해결방법

우선 DP에 저장될 값은, 해당 계단까지 오기까지 얻을 수 있는 점수의 최댓값이다.

int[] stairs = new int[N + 1];
int[] dp = new int[N + 1];

 

그렇기 때문에 계단의 점수를 저장할 stairs 배열과 dp 배열은 모두 N 개의 계단을 가지도록 만들어준다.

( N + 1은 0번째에 0을 넣어 시작점을 만들어주기 위함)

 

dp[1] = stairs[1];
dp[2] = stairs[1] + stairs[2];

 

dp[0]은 시작점이라 0 그대로 유지하고,

dp[1]은 첫번째 계단이므로 무조건 최댓값이 첫번째 계단의 점수와 같다.

dp[2]도 첫번째와 두번째 계단을 모두 밟은 값이 최댓값이 되므로 첫번째와 두번째 계단의 점수 합과 같다.

 

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

 

그리고, 가장 중요한 점화식 부분이다.

어떤 값과 어떤 값을 비교하여 dp를 채울 것인지 고민해보았는데,

 

현재 계단을 밟을때에 2가지 선택지가 있다.

A -- 전전 계단(i -2)을 밟지 않고, 이전 계단(i - 1)을 밟고 현재 계단에 도달할지,

B -- 전전 계단(i -2)을 밟고,  이전 계단(i - 1)을 밟지 않고 현재 계단에 도달할지,

이 둘 중에 하나는 꼭 해야 현재 계단을 밟을 수 있다. 

 

그리고 그 전까지의 점수 합도 고려해야하므로,

A -- 전전전 계단(i -3)까지의 최댓값 + 이전 계단 점수

B -- 전전 계단(i - 2)까지의 최댓값

 

이 둘을 비교하여 높은 값을 저장하면 된다!

 

그리고, 현재 계단의 점수 값을 더하고 dp[i]에 저장하면 된다.

 

 

if (N == 1)
{
   System.out.println(stairs[1]);
   return ;
}

 

추가로, N 값이 1일때 위의 코드만으로 돌려버리면,

dp[2]에서 IndexOutOfBounds 오류가 뜬다.

 

그를 방지하기 위해 N이 1일 때 바로 현재 계단 값을 바로 출력하고 끝내면 된다.

 

3. 코드 및 결론

[ 전체 코드 ]

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 N = Integer.parseInt(br.readLine());
       
       int[] stairs = new int[N + 1];
       
       for (int i = 1; i <= N; ++i)
       {
    	   stairs[i] = Integer.parseInt(br.readLine());
       }
       
       int[] dp = new int[N + 1];
       
       if (N == 1)
       {
    	   System.out.println(stairs[1]);
    	   return ;
       }
       
       dp[1] = stairs[1];
       dp[2] = stairs[1] + stairs[2];
       
       for (int i = 3; i <= N; ++i)
       {
    	   dp[i] = Math.max(dp[i - 3] + stairs[i - 1], dp[i - 2]) + stairs[i];
       }
       
       System.out.println(dp[N]);
    }
}

 

[ 결론 ]

 

DP 문제도 정말 오랜만에 풀다보니, DP 테이블을 만드는 것도 너무 익숙치 않았다.

늘 생각하지만 다양하게 다 복습해가면서 풀자.

 

그리고 이 문제는 특히 식을 짜기 복잡했는데, 이런 문제를 자주 풀어봐야 이런게 바로 눈에 보일 것 같다.