BOJ-2579 계단 오르기

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

문제 소개

주어진 계단과 조건 하에서 얻을 수 있는 최대의 점수를 구하는 문제이다.

문제 풀이

scores라는 dictionary는 key값으로 현재 계단 위치를 갖고, value값으로 현재 위치에 1칸 상승으로 도착했을 때의 누적 점수와 2칸 상승으로 도착했을 때의 누적 점수를 리스트로 가진다.

시작에 해당하는 0번째 계단과 1번째 계단의 점수값을 초기화해주면 나머지 계단은 반복문을 통해 이전의 계단 값을 참조해 가며 점수를 누적시키며 구할 수 있다.

• 특정 계단 위치에 1칸 상승으로 올라왔다면 그 이전 계단에는 무조건 2칸 상승으로 도착했을 것이다. 그 이유는 이전 계단에 1칸 상승으로 도착했다고 가정하면 2번 연속 1칸 상승을 의미하며 그것은 문제에서 연속된 세 개의 계단을 밟으면 안된다는 조건에 맞지 않기 때문이다.

  예외로 0번째 계단과 1번째 계단을 연속해서 오르는 경우가 있는데, 반복문은 2번째 계단의 점수를 계산하는 것부터 시작하므로 문제를 푸는 데에는 지장이 없다.

• 특정 계단 위치에 2칸 상승으로 올라왔다면 그 이전 계단에는 1칸 상승으로 도착했을 수도 있고 2칸 상승으로 도착했을 수도 있다. 문제에서 요구하는 것은 총 점수의 최댓값이므로 두 경우 중 큰 값으로 scores에 저장한다.

계단의 개수를 a라고 했을 때, 총 점수의 최댓값은 max(scores[a - 1])이다. scores[a - 1]이 마지막(a - 1번째) 계단에 1칸 상승으로 도착한 경우와 2칸 상승으로 도착한 경우를 원소로 갖는 리스트이기 때문이다.

코드

from sys import stdin
input = stdin.readline

a = int(input())
stairs = [int(input()) for _ in range(a)]

# 계단의 개수가 하나라면 0번째 계단의 점수를 바로 출력하고 마친다.
if a == 1:
    print(stairs[0])
    exit()

# scores의 key는 현재 계단 위치, value의 두 값은 각각 1칸 상승으로 올라왔을 때의 점수와 2칸 상승으로 올라왔을 때의 점수를 의미한다.
scores = {key: [0, 0] for key in range(a)}
scores[0][0] = stairs[0]
scores[1][0] = stairs[0] + stairs[1]
scores[1][1] = stairs[1]

for i in range(1, a - 1):
    # 1칸 올라간 경우는 이전에 2칸 올랐음(시작 제외)
    scores[i + 1][0] = scores[i][1] + stairs[i + 1]
    # 2칸 올라간 경우는 이전에 1칸 또는 2칸 올랐음
    scores[i + 1][1] = max(scores[i - 1][0], scores[i - 1][1]) + stairs[i + 1]  
print(max(scores[a - 1]))