코딩테스트 대비/BOJ
[Baekjoon/Python] 1149번: RGB거리 - 효과는 굉장했다!
bluetag_boy
2022. 3. 28. 02:22
반응형
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
알고리즘 분류
- 다이나믹 프로그래밍
SOLUTION
import sys
N = int(sys.stdin.readline())
RGB_cost = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
for i in range(1,N): # 이전 집 색깔과 겹치지 않는 것이 Key Point
RGB_cost[i][0] = min(RGB_cost[i-1][1], RGB_cost[i-1][2]) + RGB_cost[i][0] # 빨간색을 색칠하는 비용
RGB_cost[i][1] = min(RGB_cost[i-1][0], RGB_cost[i-1][2]) + RGB_cost[i][1] # 초록색을 색칠하는 비용
RGB_cost[i][2] = min(RGB_cost[i-1][0], RGB_cost[i-1][1]) + RGB_cost[i][2] # 파란색을 색칠하는 비용
print(min(RGB_cost[N-1][0], RGB_cost[N-1][1], RGB_cost[N-1][2])) # 색칠한 비용들 중 가장 최소비용을 출력