728x90
문제 (링크)
https://www.acmicpc.net/problem/2579
나의 풀이
n = int(input())
stairs = [0] * (n + 1)
d = [0] * (n + 1)
for i in range(1, n + 1):
stairs[i] = int(input())
# 계단은 한 번에 한 개 or 두 개
# 세 개 연속 X
# 마지막 무조건 도착
if n == 1:
print(stairs[n])
elif n == 2:
print(stairs[1] + stairs[2])
else:
d[1] = stairs[1]
d[2] = stairs[1] + stairs[2]
d[3] = max(stairs[2] + stairs[3], stairs[1] + stairs[3])
for i in range(4, n+1):
d[i] = max(d[i-3] + stairs[i] + stairs[i-1], d[i-2] + stairs[i])
print(d)
코드 설명 및 접근법
동적계획법의 핵심은 첫 몇 개의 케이스를 하드코딩해주고 나머지 경우들을 점화식을 통해 처리하는 것 같다.
연속된 세 개의 계단을 밟으면 안된다는 조건 때문에 분기문을 사용해야하나 고민했지만, 그럴 필요 없이 경우의 수 두 가지를 만들어 점화식으로 세워주면 꽤 쉽게 해결되는 문제였다.
여기서 경우의 수란, 계단을 어떻게 올라갈지에 대한 경우의 수가 아닌 어떻게 올라왔는지에 대한 경우의 수이다.
i 번째 계단에 도달했다고 가정할 때, 이전에 밟은 계단의 경우의 수는 2가지가 존재한다.
i - 3번째 계단을 밟고, i - 2번째 계단을 밟은 후 i 번째 계단에 도달한 경우와
i - 1번째 계단을 밟고, i 번째 계단에 도달한 경우이다. (이 경우에는 i - 2번째 계단을 밟지 않은 것으로 간주한다)
그리고 이 두 가지 경우의 수 중 더 큰 값을 리스트에 기록해주면 된다.
* 3번째 계단까지는 하드코딩을 해주었기 때문에, n의 값이 1이나 2가 들어올 경우 예외처리를 해주지 않으면 인덱스 에러가 난다.
'알고리즘 > 문제풀이' 카테고리의 다른 글
[백준] 4179번 불! - 파이썬(Python) (0) | 2021.09.04 |
---|---|
[백준] 1753번 최단경로 - 파이썬(Python) (0) | 2021.08.22 |
[백준] 1931번 회의실 배정 - 파이썬(Python) (0) | 2021.08.01 |
[백준] 13305번 주유소 - 파이썬(Python) (0) | 2021.07.28 |
[백준] 1003번 피보나치 함수 - 파이썬(Python) (0) | 2021.04.26 |