1. 문제
계단 오르기 게임은 계단 아래의 시작점에서 계단 꼭대기의 끝점까지 이어지는 게임입니다. 에서와 같이
예를 들어 다음과 같은 경우
계단을 오르는 규칙이 있습니다.
- 계단은 한 번에 한 단계 또는 두 단계로 오를 수 있습니다. 즉, 한 단계를 밟고 있는 동안 다음 단계 또는 단계를 오를 수 있습니다.
- 연속으로 세 단계를 모두 밟지 마십시오. 그러나 시작점은 계단에 포함되지 않습니다.
- 마지막 층계참으로 들어가야 합니다.
따라서 첫 번째 계단을 밟은 후 두 번째 또는 세 번째 계단을 오를 수 있습니다. 그러나 첫 번째 단계를 밟았다가 네 번째 단계로 올라가거나 첫 번째, 두 번째, 세 번째 단계를 차례로 밟을 수는 없습니다.
각 단계의 점수가 주어진 경우 이 게임에서 달성할 수 있는 최대 총 점수를 찾는 프로그램을 작성하십시오.
2. 입력
단계 수는 입력의 첫 번째 줄에 제공됩니다.
두 번째 행부터 시작하여 각 수준의 점수가 가장 낮은 수준부터 순서대로 행당 하나씩 제공됩니다. 계단의 수는 300 이하의 자연수이고, 계단에 적힌 점수는 10,000 이하의 자연수이다.
6
10
20
15
25
10
20
3. 종료
첫 번째 줄은 계단 오르기 게임에서 달성할 수 있는 최대 총 점수를 보여줍니다.
75
4. 코드
import sys
input = sys.stdin.readline
n = int(input())
stairs = (int(input()) for _ in range(n))
result = (0 for _ in range(n))
# n이 2이하면 stairs의 합이 결과값
if n < 2:
result(n-1) = sum(stairs)
else:
result(0) = stairs(0)
result(1) = result(0) + stairs(1)
for i in range(2,n):
# val(6) = max(val(~3)+5+6, val(~4)+6)
result(i) = max(result(i-3)+stairs(i-1)+stairs(i),result(i-2) + stairs(i))
print(result(n-1))
5. 솔루션 설명
① 초기값 n과 단계값을 입력합니다.
② 0으로 구성된 n-long 결과 목록을 생성합니다.
③ n이 2보다 작으면 계단의 합을 result(n-1)에 넣는다.
④ n이 2보다 크면 결과(0), 결과(1) 계단(0), 결과(0) + 계단(1)을 바꿉니다.
⑤ 2부터 n까지 반복문을 실행
– 결과(i)에 3노드 합 + 1노드 계단 값 + i노드 계단 값 또는 2노드 노드 합 + i노드 계단 값 아래에 큰 수를 대입한다.
⑥ 결과값(n-1)을 결과값으로 출력합니다.
6. 느낀 점
점화를 찾기가 어렵습니다. dp 문제는 좀 더 풀어봐야 할 것 같습니다.