문제
https://www.acmicpc.net/problem/2579
풀이
- 계단은 한 번에 1 or 2 계단씩 오를 수 있다.
- 연속된 3계단을 밟을 순 없다.
- 단, 시작점은 계단에 포함 x
- 마지막 계단은 무조건 밟아야 한다.
- 밟을 수 있는 계단의 최대값을 출력해야 한다.
DP를 이용하면 될 것 같으니 점화식부터 작성해봅시다.
첫 번째 계단: 올라갈 수 있는 방법이 하나 밖에 없으니
dp[0] = arr[0]두 번째 계단: 연속으로 계단을 밟는 방법, 1번 계단을 건너뛰고 2번 계단을 밟는 방법이 있습니다.
그러나 우리는 밟을 수 있는 계단의 최대값을 출력해야 되기 때문에 두 계단을 모두 밟는 방법만 고려하면 되기 때문에dp[1] = arr[0] + arr[1]세 번째 계단: 1번 계단을 밟고 3번 계단을 밟는 방법, 2번 계단을 밟고 3번 계단을 밟는 방법이 있습니다. 마찬가지로 최대값만 고려하면 되기 때문에
max()를 이용해 값을 구합니다.dp[2] = max(arr[0] + arr[2], arr[1] + arr[2])
여기까지는 굉장히 단순합니다.
다음 계단부터는 잘 살펴봐야 합니다.
네 번째 계단: 1번 + 2번 + 4번, 1번 + 3번+ 4번, 2번 + 4번
총 3가지 경우의 수가 있습니다.
여기서 문제를 다시 살펴보면, 연속된 3계단을 밟을 순 없다. 라고 적혀있습니다.
그러기 때문에 1번 계단과 2번 계단을 밟으면 무조건 적으로 4번 계단을 밟아야 합니다.
1번 계단을 밟고 2번 계단을 밟지 않으면 3번 계단을 밟아야만 4번 계단을 밟을 수 있기 때문에 "1번 + 3번 + 4번"이란 방법이 나옵니다.
1번 계단을 밟지 않고 4번 계단까지 올라오려면 2번 계단을 밟고 4번 계단을 밟는 방법이 있습니다.(연속된 3계단을 밟으면 안 되기 때문에 3번 계단 x)
여기서 공식이 보이지 않습니까?
- 1번 계단을 밟게 되면, 2번이나 3번 계단을 밟은 후에 4번 계단을 밟아야 합니다. (1번 + 2번 + 4번은 2번 + 4번과 같으므로 이는 다음 점화식에 적용되므로 1번 + 3번+ 4번만 고려하면 됩니다.)
- 2번 계단을 밟게 되면, 바로 4번 계단을 밟아야 합니다.
이를 번째 계단에도 적용하게 되면
# 첫 번째 조건
dp[i-3] + arr[i-1] + arr[i]
# 두 번째 조건
dp[i-2] + arr[i]해당 방식을 가지고 코드를 작성했으나, IndexError가 발생했습니다.
왜인지 하니 n의 값이 2보다 작을 경우 dp[2]를 선언하게 되면 오류가 발생될 수 있기 때문입니다.
아래는 수정된 코드입니다.
코드
import sys
input = sys.stdin.readline
n = int(input())
arr = [int(input()) for _ in range(n)]
dp = [0] * n # 저장할 배열 선언
if n <= 2: # 2이하일 경우 계단의 모든 합 출력
print(sum(arr))
else:
dp[0] = arr[0]
dp[1] = arr[0] + arr[1]
dp[2] = max(arr[0] + arr[2], arr[1] + arr[2])
for i in range(3,n):
dp[i] = max(dp[i-2] + arr[i], dp[i-3] + arr[i-1] + arr[i])
print(dp[-1])