RGB거리

1149번: RGB거리

 

나의 풀이

import sys

def _RGB(n, map_list):
    for i in range(1, n):
        for j in range(3):
            map_list[i][j] += min(map_list[i-1][:j] + map_list[i-1][j+1:])
    return min(map_list[-1])

n = int(sys.stdin.readline())
map_list = []
for _ in range(n):
    map_list.append(list(map(int, sys.stdin.readline().rstrip().split())))
print(_RGB(n, map_list))

 

시간 복잡도

for i in range(1, n) : 각 행 순회하며 최솟값 치환 ( 선형 시간 )
해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )