[백준 2024/02/27] 2579번 계단 오르기

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

1. 접근 방법

처음에는, DFS로 구현, memoization을 이용했지만, 왜인지 모르겠지만, 초반에 에러가 나서 다른 방법을 찾아보게 되었다.

(아직도 이유를 모르겠다.)

 

dp[0], 즉 첫 계단에서의 최댓값 수는, nums[0] 일 것이다. 하나의 경우의 수밖에 없기 때문이다.

 

n 이 1 보다 크다면, dp[1] 의 최댓값은 첫 번째 계단을 밟고, 두 번째 계단을 밟는 것이 될 것입니다.

 

세 번째 계단 이상이라면, 첫 번째 계단을 밟고 세 번째 계단을 밟는 경우 혹은 두 번째 계단을 밟고 세 번째 계단을 밟는 경우가 될 것이다.

여기서 위에서 구현하려고 헸던 memoization 코드가 틀린 이유가 생각이 났다. 첫 번째 계단을 건너뛸 수 있는 경우를 생각하지 못했다.

 

4 번째 계단, (index로는 3번) 이상의 경우 패턴을 가지고 있기에, 유사하게 풀어주었다.

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

 

현재 있는 index로 접근 하는 방법 중에, 2칸 이동하는 경우 or 2칸 1칸 이동하는 경우를 대상으로 max를 찾는 방식으로 문제를 해결하였다.

 

만약, 1칸 2칸도 max 대상으로 해서 문제를 해결할 경우, 3칸을 연속해서 이동하는 경우가 포함 되므로, 포함해서는 안된다.

또한 1칸 2칸으로 이동하게 되는 경우 2칸 이동하는 경우와 경로가 겹치기 때문에, 포함해서 안된다.

 

이런식으로 풀게 된다.

 

2. 코드

n = int(input())
nums = [int(input()) for _ in range(n)]

dp = [0 for _ in range(n)]

dp[0] = nums[0]
if n > 1:
    dp[1] = nums[0] + nums[1]
if n > 2:
    dp[2] = max(nums[0] + nums[2], nums[1] + nums[2])

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

print(dp[-1])