백준 2579 (python): 계단 오르기

t = int(input())

stairs = [0]
d = [0 for _ in range(t+1)]

for _ in range(t):
    stairs.append(int(input()))

for i in range(1, t+1):
    if i <= 2:
        d[i] = d[i-1] + stairs[i]
    else:
        d[i] = max(d[i-3] + stairs[i-1] + stairs[i], d[i-2] + stairs[i])

print(d[-1])

 

이틀에 걸쳐서 풀었다.. 

처음에는 flag 변수 선언해서 풀었는데.. dp 가 그럴리가 없다는 걸 깨닫고 코드 수정함 -,-

 

t = int(input())

stairs = []
flag = True
d = [0 for _ in range(t)]

for _ in range(t):
    stairs.append(int(input()))
    
d[0] = stairs[0]

for i in range(1, t):
    if i == 1:
        d[i] = d[i-1] + stairs[i]
        flag = False
    else:
        if flag == False:
            d[i] = d[i-2] + stairs[i]
            if d[i] <= d[i-1]:
                flag = True
                d[i] = d[i-1]
    
print(max(d))

 

기존 코드 ㅋㅋㅋ 마지막 max(d)도 어이없음

마지막 계단 무조건 밟아야 된다잖니?!

 

dp는 점화식 세우는 게 가장 중요하다!

그림 그려서 생각 잘 해보자 글구! d 배열은 본인 포함해야 한다!!!