RGB거리 2 ( 17404 번 )

17404번: RGB거리 2

 

🧠 알고리즘

N개의 집이 일렬로 있고, 각 집은 빨강(R), 초록(G), 파랑(B) 중 하나로 칠해야 함.

첫 번째 집의 색을 R, G, B 각각으로 고정한 3가지 경우를 시도
각 경우마다 DP를 수행하면서 최소 비용 계산
마지막 집의 색이 첫 번째와 다르면 결과 후보로 인정

 

🧾 코드

import sys

def _main(n, map_list):
    answer = float('inf')
    for start in range(3): # 3가지 케이스
        rgb = [[float('inf')] * 3 for _ in range(n)]
        rgb[0][start] = map_list[0][start]

        for idx in range(1, n):
            rgb[idx][0] = map_list[idx][0] + min(rgb[idx - 1][1], rgb[idx - 1][2])
            rgb[idx][1] = map_list[idx][1] + min(rgb[idx - 1][0], rgb[idx - 1][2])
            rgb[idx][2] = map_list[idx][2] + min(rgb[idx - 1][0], rgb[idx - 1][1])

            if idx == (n - 1): # 마지막 이면..
                for last_idx in range(3):
                    if last_idx != start:
                        answer = min(answer, rgb[idx][last_idx])
        
    return answer


n = int(sys.stdin.readline().rstrip())
map_list = [tuple(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]

print(_main(n, map_list))

 

 

⏱️ 시간 복잡도

for idx in range(1, n) : n 만큼 순회

해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )