2579번: 계단 오르기

2579번: 계단 오르기

DP 문제다.

계단을 오르면서 얻을 수 있는 총 점수의 최댓값을 출력하면 된다.

규칙은 크게 3가지가 존재한다.

1. 계단은 한번에 한 계단, 혹은 두 계단 씩 오를 수 있다.

2. 연속된 세 계단을 밟을 수 없다.

3. 마지막 계단을 반드시 밟아야 한다.

 

1번, 3번 조건은 쉽지만 2번 조건이 까다로웠다.

연속된 세 개의 계단을 밟을 수 없으므로 dp테이블을 갱신할 때, 이전 dp값에서 연속된 계단을 밟았는지 아닌지 판단하는 로직이 필요하다고 생각했다.

그래서 count라는 변수를 도입해서 이전 계단을 안 밟았으면 0, 밟았으면 1로 해서 구해보려고 했으나, 로직이 너무 복잡해지고 이렇게 푸는게 아니라는 생각이 들었다.

 

그래서 결국 살짝 구글링을 참고해서 풀었다.

# 2579번: 계단 오르기
n = int(input()) # 계단의 개수
dp = [0] * 301 # dp 테이블
arr = [0]


for _ in range(n):
    arr.append(int(input()))

dp[1] = arr[1]
if n >= 2: # n이 1인 경우, arr[2]에 접근할 수 없어 런타임 에러 발생
    dp[2] = arr[1] + arr[2]

for i in range(3, n+1):
    dp[i] = max(dp[i-3] + arr[i-1] + arr[i], dp[i-2] + arr[i])


print(dp[n])

핵심 점화식은

dp[i] = max(dp[i-3] + arr[i-1] + arr[i], dp[i-2] + arr[i])

다.

 

만약 i번째 계단을 밟았을 때의 최댓값을 구한다고 생각해보자.

그렇다면, 이전 계단을 밟았을 경우와 안 밟았을 경우로 나눌 수 있다.

1. i-1번째 계단을 밟았을 경우 -> i-2번째 계단을 밟을 수 없으므로 i-3번째까지의 합의 최댓값에다가 i-2번째 계단 값 + i-1번째 계단값을 더해주면 i-1번째 계단을 밟은 경우의 i번째 계단을 밟았을 때의 최댓값이 나온다.

dp[i-3] + arr[i-1] + arr[i]

2. i-1번째 계단을 밟지 않았을 경우 -> i-2번째 계단을 밟을 수 있고, 이전 계단은 상관없으므로 i-2번째까지의 합의 최댓값에다가 i번째 계단값을 더해주면 된다.

dp[i-2] + arr[i]

 

이 문제가 이전 문제보다 티어는 더 낮던데, 이 문제는 잘 안풀렸다.

점화식만 생각하면 되는 문제.