[백준 2579번] 계단 오르기

이번 문제는 연속으로 3칸을 밟을 수 없고 한번에 1칸이나 2칸씩 계단을 오를 수 있다는 가정 하에, 마지막 도착 계단까지 도착하는데 얻을 수 있는 총 점수의 최댓값을 구하는 문제이다.

 

먼저 이 문제는 완전탐색으로 풀 경우에는 N이 최대 300이기 때문에 2^300 의 경우의 수로 인해 시간초과가 발생하게 된다. 따라서 O(n) 시간복잡도로 풀 수 있는 DP 알고리즘을 사용해야 한다.

 

처음에 이 문제를 풀이했을 때는 dp 테이블을 1차원 배열로 선언해서 점화식을 도출하려고 했었는데, 1차원으로 선언하게 되면 점화식을 세우고 싶어도 연속한 세 계단을 모두 밟아서는 안 된다는 제약 조건을 점화식에 넣을 방법이 없다.(연속해서 몇 개의 계단을 밟았는지 확인할 수 없음)

 

따라서 i번째 계단까지 밟았을 때의 총 점수의 최댓값과 연속해서 밟은 계단수인 j번까지 나타내는 2차원 배열로 선언해야 한다.

 

즉, D[i][j] = 현재까지 j개의 계단을 연속해서 밟고 i번째 계단까지 올라섰을 때 점수 합의 최댓값, 단 i번째 계단은 반드시 밟아야 함으로 정의한다.(지금까지 몇 개의 계단을 밟았는지에 대한 정보가 추가로 있어야 점화식을 세울 때 계단을 오르는 규칙을 고려할 수 있기 때문)

 

for i in range(2,n):
   # i-2칸에서 연속해서 한칸을 밟았을 경우와 두칸을 밟았을 경우 중 더 큰 값 선택
   dp[i][0] = max(dp[i-2][0],dp[i-2][1]) + scores[i] 
   # i-1칸에서 연속해서 한칸을 밟았을 경우에 현재 칸의 값 더해주기
   dp[i][1] = dp[i-1][0] + scores[i]

여기서 dp[0][0], dp[0][1], dp[1][0], dp[1][1]을 초기값으로 설정한 뒤 다음과 같은 점화식으로 DP 테이블을 Bottom-up 방식으로 채운 뒤 마지막 계단에서의 총 점수 최댓값인 dp[n-1][0]과 dp[n-1][1] 중 더 큰 값을 출력하면 된다.

 

배운 점 및 느낀 점

1. DP는 여러 개의 하위 문제를 먼저 푼 후에 그 결과를 쌓아올려서 주어진 문제를 해결하는 알고리즘이다.
2. 즉, 문제를 해결하기 위한 점화식을 찾아낸 후 점화식의 항을 밑에서부터 차례로 구해나가서 답을 알아내는 형태의 알고리즘이다.
3. DP를 풀기 위해서는 테이블을 먼저 어떻게 정의할지 고민하고, 초기값을 설정한 뒤 점화식을 도출하여 풀이해야 한다.
4. 테이블을 1차원으로 선언했을 때 제약사항을 고려하지 못한다면 제약사항을 고려할 수 있는 2차원 배열로 선언해야 한다. ⭐️