[BOJ] 2579 - 계단 오르기

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

2579번: 계단 오르기

n = int(input())
data = [0] * 300
for i in range(n):
    data[i] = int(input())

dp = [0] * 300
dp[0] = data[0]
dp[1] = data[0] + data[1]
dp[2] = max(data[0] + data[2], data[1] + data[2])

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

print(dp[n - 1])

data를 입력받을 때 사실 이렇게 리스트를 먼저 초기화 한 다음에 대입하는 방법을 선호하지 않고 딱 n개만큼 데이터를 입력받는 것을 좋아하는데 이 경우 n이 1일 때 dp[2] 부분을 초기화하며 data[2]를 접근하게 되면 오류가 나기 때문에 예외처리를 해주지 않기 위해서 위와 같은 방식으로 data를 입력받았다.

 

이 문제에서 마지막 계단은 무조건 밟아야 하므로 이 경우는 다음과 같이 나눌 수 있다.

1. 마지막 계단의 전 계단을 밟은 경우
2. 마지막 계단의 전 계단을 밟지 않은 경우

첫 번째 경우가 성립하기 위해서는 연속해서 3개의 계단을 밟지 못하는 규칙에 따라 n - 3 번째 계단을 밟고 n - 1 번째 계단을 밟아야 한다. 따라서 점화식은 dp[i] = dp[i - 3] + data[i - 1] + data[i]가 된다.

 

두 번째 경우는 3개의 계단을 밟지 못하는 규칙을 생각할 필요가 없다. 점화식은 dp[i] = dp[i - 2] + data[i]가 된다.

 

이 두 가지 경우 중 최댓값을 갱신해나가며 마지막 값을 출력하면 정답을 얻을 수 있다.

 

주목할 점은 점화식에서 i - 3이 사용되기 때문에 인덱스 범위를 맞추기 위해서 dp[2]까지는 for 문 밖에서 하드 코딩해주었다.

 

느낀 점

아직 점화식 떠올리는 것이 너무 어렵다. 특히 중복되어 들어가는 값이 있는지 없는지 판단하는게 너무 헷갈린다.