내려가기 ( 2096번 )

2096번: 내려가기

 

나의 풀이

import sys

def _main(n, n_list):
    # 현재 행의 최소값 및 최대값을 저장하는 리스트
    prev_min = n_list[0]
    prev_max = n_list[0]

    for i in range(1, n):
        curr_min = [0] * len(n_list[0])
        curr_max = [0] * len(n_list[0])

        for j in range(len(n_list[0])):
            # 최소값 계산
            if j == 0:
                curr_min[j] = min(prev_min[j], prev_min[j + 1]) + n_list[i][j]
            elif j == len(n_list[0]) - 1:
                curr_min[j] = min(prev_min[j], prev_min[j - 1]) + n_list[i][j]
            else:
                curr_min[j] = min(prev_min[j], prev_min[j - 1], prev_min[j + 1]) + n_list[i][j]

            # 최대값 계산
            if j == 0:
                curr_max[j] = max(prev_max[j], prev_max[j + 1]) + n_list[i][j]
            elif j == len(n_list[0]) - 1:
                curr_max[j] = max(prev_max[j], prev_max[j - 1]) + n_list[i][j]
            else:
                curr_max[j] = max(prev_max[j], prev_max[j - 1], prev_max[j + 1]) + n_list[i][j]

        # 현재 행을 이전 행으로 업데이트
        prev_min, prev_max = curr_min, curr_max

    # 마지막 행에서 최소값과 최대값을 반환
    return f"{max(prev_max)} {min(prev_min)}"

# 입력 처리
n = int(sys.stdin.readline())
n_list = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]

# 결과 출력
print(_main(n, n_list))

 

시간 복잡도

for i in range(1, n) : n 만큼의 연산을 수행 ( 선형 시간 복잡도 )
    # 내부 로직은 상수 시간
해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )