[백준알고리즘] 2096번: 내려가기 -Python

[백준알고리즘] 2096번: 내려가기 -Python

https://www.acmicpc.net/problem/2096

2096번: 내려가기

최대와 최소를 동시에 구해주어야 한다.

 

처음에는 large와 small을 구해주는 리스트를 처음에 주어진 크기와 같은 크기로 이중 리스트를 만들어 주었었다.

 

메모리 제한이 4MB이기 때문에 메모리 초과가 발생하게 되는데, 그래서 아래처럼 크기가 3인 리스트 두 개를 이용해서 최대 점수와 최소 점수를 구하도록 했다.

n = int(input())
table = [list(map(int, input().split())) for _ in range(n)]
large = table[0]
small = table[0]

for i in range(1, n):
    large = [max(large[0], large[1]) + table[i][0],\
            max(large[0], large[1], large[2]) + table[i][1],\
            max(large[1], large[2]) + table[i][2]]
    small = [min(small[0], small[1]) + table[i][0],\
            min(small[0], small[1], small[2]) + table[i][1],\
            min(small[1], small[2]) + table[i][2]]

print(max(large), min(small))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다