[BOJ]2579:階段を登る

🔒 例

>> 6
>> 10
>> 20
>> 15
>> 25
>> 10
>> 20

75

🔧 に答える

1. n = int(sys.stdin.readline().rstrip())
2. stairs = [10, 20, 15, 25, 10, 20] 리스트 저장
3. '마지막 도착 계단은 반드시 밟아야 한다' -> 뒤에서 마지막 계단을 기준으로 생각
	ㄴ 3계단 연속 밟기 X
    3.1 n번째 계단 + (n-1) 계단 => stairs[n] + stairs[n-1] + dp[n-3] 
    3.2 n번째 계단 + (n-2) 계단 => stairs[n] + dp[i-2]
4. 시작점은 계단에 포함되지 않는다. -> 시작값 = 첫번째 계단 값     
5. n에 따라 dp 예외처리 !

🔑 答案用紙

import sys

n = int(sys.stdin.readline().rstrip())
stairs = [0]
for _ in range(1, n + 1):
    stairs.append(int(sys.stdin.readline().rstrip()))

# n이 3이하일 경우, 계단 합 = 최댓값
if n < 4:
    print(sum(stairs))
else:
    dp = [0 for _ in range(n + 1)]
    dp[1] = stairs[1]
    dp[2] = dp[1] + stairs[2]
    # n이 4이상일 때를 위한 dp 값이므로 3계단 연속 불가 조건 고려하여 작성 
    dp[3] = max(stairs[1], stairs[2]) + stairs[3]
    
    # n번째 계단 + (n-1) 계단 + dp[n-3]
    # n번째 계단 + dp[n-2]
    
    for i in range(4, n + 1):
        dp[i] += (stairs[i] + max(dp[i - 2], dp[i - 3] + stairs[i - 1]))
        
    print(dp[n])

💡 コンセプト