2019.02.14) 백준 2579번 풀이 (PyPy3)

다이나믹 프로그래밍은 반복하여 저장하는 도중 언제 어디서 필요없는 정보를 버리고 가볍게 하느냐가 관건이다.

c = int(input())
l = list()
 
for i in range(c):
    # 역순으로 계산할거라 insert 사용
    l.insert(0, int(input()))
 
# 0,1,2번쨰 스텝인 현재 스텝 수를 저장
r = [[0, l[0], 0]]
 
for i in range(1, c):
    # 3번째 까지는 무조건 끝을 밟아야 하는 규칙때문에 수동으로 넣음
    if i == 1:
        r.append([r[0][1], 0, r[0][1] + l[1]])
    elif i == 2:
        r.append([r[1][2], r[1][0] + l[2], 0])
    elif i == 3:
        r.append([r[2][1], r[2][0] + l[3], r[2][1] + l[3]])
    else:
        # 스텝 0번째(다음번에 무조건 밟기)는 전의 1번째와 2번째가 스텝을 포기하면서 경우의 수가 늘어남
        # 두개를 비교해서 큰쪽만 0번째에 넣음
        # 1번째랑 2번째는 각각 0번째랑 1번째가 한번 더 밟는 경우밖에 없음
        r.append([r[i-1][1] if r[i-1][1] > r[i-1][2] else r[i-1][2],
                  r[i-1][0] + l[i],
                  r[i-1][1] + l[i]])
 
# ex) r -> [[0, 20, 0], [20, 0, 30], [30, 45, 0], [45, 45, 60], [60, 65, 65], [65, 70, 75]]
print(max(r[-1]))