백준 / 내려가기 / 2096번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 내려가기 / 2096번 (골드 5단계)

문제 사이트: https://www.acmicpc.net/problem/2096

 

문제 설명

---

나의 풀이

import sys
input = sys.stdin.readline


def main():
    n = int(input())

    a, b, c = map(int, input().split())
    prev_max = [a, b, c]
    prev_min = [a, b, c]

    for _ in range(1, n):
        a, b, c = map(int, input().split())

        max0 = max(prev_max[0], prev_max[1]) + a
        max1 = max(prev_max[0], prev_max[1], prev_max[2]) + b
        max2 = max(prev_max[1], prev_max[2]) + c

        min0 = min(prev_min[0], prev_min[1]) + a
        min1 = min(prev_min[0], prev_min[1], prev_min[2]) + b
        min2 = min(prev_min[1], prev_min[2]) + c

        prev_max = [max0, max1, max2]
        prev_min = [min0, min1, min2]

    print(max(prev_max), min(prev_min))


if __name__ == "__main__":
    main()

---

※ 알아야 할 것

# 문제점
# 모든 행을 탐색하는 과정에서 메모리 초과가 발생함
def solution(n, down):
    # 가장 깊은 배열을 찾는다.
    new_down = copy.deepcopy(down)

    for i in range(1, n):
        new_down[i][0] = max(new_down[i][0] + new_down[i - 1][0], new_down[i][0] + new_down[i - 1][1])
        new_down[i][1] = max(new_down[i][1] + new_down[i - 1][0], new_down[i][1] + new_down[i - 1][1], new_down[i][1] + new_down[i - 1][2])
        new_down[i][2] = max(new_down[i][2] + new_down[i - 1][1], new_down[i][2] + new_down[i - 1][2])

    max_value = max(new_down[n - 1])

    # 가장 깊은 배열을 찾는다.
    new_down = copy.deepcopy(down)

    for i in range(1, n):
        new_down[i][0] = min(new_down[i][0] + new_down[i - 1][0], new_down[i][0] + new_down[i - 1][1])
        new_down[i][1] = min(new_down[i][1] + new_down[i - 1][0], new_down[i][1] + new_down[i - 1][1], new_down[i][1] + new_down[i - 1][2])
        new_down[i][2] = min(new_down[i][2] + new_down[i - 1][1], new_down[i][2] + new_down[i - 1][2])

    min_value = min(new_down[n - 1])

    print(max_value, min_value)

위 코드와 같이 모든 행을 볼 필요없고 이전의 행만 참고하면 됩니다!