문제 설명

전체 코드

n = int(input())

s = [0 for i in range(301)]
dp = [0 for i in range(301)]

for i in range(n):
    s[i] = int(input())

dp[0] = s[0]
dp[1] = s[0] + s[1]
dp[2] = max(s[1] + s[2], s[0] + s[2])

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

print(dp[n - 1])

해결 방법

역시 동적계획법은 정말 어렵다. 이전에 풀었을때 답을 보았었는데 이번에도 저번에 풀었던 문제를 봤다. 이 푸는 느낌을 기억해야겠다.

문제 해결방법은 4가지로 나누어서 풀어야 한다.

• 가장 중요한 것은 마지막 계단의 전을 밟았는가
• 마지막 계단의 전을 밟지x
• 이 것을 하기 전에 먼저 n = 1 , 2, 3, 4 일때 등등을 생각하고
• 규칙이 구해지는 때부터 점화식을 사용해서 푼다

코드를 보면 dp를 하나 선언하여 메모이제이션을 할 리스트를 만들고 dp[0]에는 첫 번째 계단 dp[1]에는 첫 번째 계단과 두 번째 계단을 밟을 경우 dp[2]에는 max(두 번째 계단 + 세 번째 계단, 첫 번째 계단 + 세 번째 계단)을 넣는다. 그 후 반복문을 사용하여 메모이제이션한 dp리스트와 s를 점화식을 이용한 코드를 이용하여 dp에 저장한다.