[백준 2579] 계단 오르기 - 파이썬

백준 2579 - 계단 오르기

 

* 풀이과정

다이나믹 프로그래밍 유형의 문제로, 규칙을 찾아 점화식을 이용한다.

1) 계단의 수 N을 입력받는다.

2) 계단의 점수를 L = [0] * (N+1) 리스트에 저장한다.

3) j 번째 계단 별 최대 점수를 저장할 dp = [0] * (N+1) 리스트를 생성한다.

4) dp 구하기

• dp[1] = L[1]
• dp[2] = L[1] + L[2]
• dp[3] = max(L[1]+L[3], L[2]+L[3])
• 3보다 큰 j번째 계단을 오를 때의 점수 최댓값은 j-1번째 계단을 밟을 때와 밟지 않을 때로 나뉜다. (j번째는 항상 밟아야 함)
  (i) j-1 번째 계단을 밟는 경우: dp[j-3] + L[j-1] + L[j]
  j-2 번째 계단을 밟을 수 없고, j-3번째 계단을 무조건 밟아야 한다. 따라서, j-3번째 계단을 오를 때까지의 최대 점수에 j-1, j번째 계단의 점수를 더하면 된다.
  (ii) j-1 번째 계단을 밟지 않는 경우: dp[j-2] + L[j]
  j-2번째 계단을 무조건 밟아야 한다. 따라서, j-2번째 계단을 오를 때까지의 최대 점수에 j번째 계단의 점수를 더하면 된다.
• 위 두가지 경우 중 더 큰 값을 max()로 선택하면 된다.

5) N이 3보다 작거나 같은 경우, 인덱스 오류가 발생하므로 if 문으로 제한해야 한다.

 

N = int(input())
L = [0]*(N+1)

# 계단 별 점수 입력받기
for i in range(1, N+1):
    L[i] = int(input())

if N >= 3:
     dp = [0] * (N+1)
     dp[1] = L[1]
     dp[2] = L[1]+L[2]
     dp[3] = max(L[1]+L[3], L[2]+L[3])

     # 3보다 큰 j번째 계단을 오를 때, 점수의 최댓값은 j-1번째 계단을 밟거나 그렇지 않은 경우로 나뉨
     # 두가지 경우 중 max 값을 dp[j]에 저장
     # 1) j-1번째 계단을 밟는 경우: j-2번째 계단을 밟지 않고 j-3번째 계단을 밟아야 하므로,
     # dp[j-3] + L[j-1] + L[j]
     # 2) j-1번째 계단을 밟지 않는 경우: j-2번째 계단을 밟아야 하므로,
     # dp[j-2] + L[j]
     for j in range(4, N+1):
          dp[j] = max(dp[j-3]+L[j-1]+L[j], dp[j-2]+L[j])

     print(dp[N])

# Index Error 방지
elif N == 2: print(L[1]+L[2])
else: print(L[1])