알고리즘/백준[baekjoon]

[baekjoon] 백준 1149번 : RGB거리 (by python 파이썬) DP 다이나믹 프로그래밍

코딩하는이씨 2022. 8. 14. 13:15
728x90
반응형

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

 

1149번: RGB거리

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나

www.acmicpc.net

 

정답 code

#RGB거리
import sys
input = sys.stdin.readline

n = int(input())
cost = []

for _ in range(n):
    r,g,b = map(int,input().split())
    cost.append([r,g,b])

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

print(min(cost[n-1]))

 

solution

cost[i][0] = i번째 집 red색상

cost[i][1] = i번째 집 green색상

cost[i][2] = i번째 집 blue색상

 

만약  i번째 집 red색상을 했다면 i-1번째 집은 green이나 blue로 색을 칠해야 한다.

따라서 green색 blue색 둘중 최솟값을 구해 i번째 레드값과 더해준다.

 

이런 방식으로 i번째 집이 green색 blue색으로 칠해졌을때 최솟값도 구해준다.

마지막 집까지 최솟값을 구하면 마지막집 r,g,b색상 별로 최솟값이 나오는데

이중 최솟값을 구해 출력해주면 된다.

 

728x90
반응형