반응형
[문제 출처]
https://www.acmicpc.net/problem/1149
[문제 풀이]
i번째 집을 R, G, B 각 색으로 칠했을 때 비용을 저장하고 n번째 집은 n-1번째 집과 색이 다르다고 했으므로
n번째 집을 x라는 색으로 칠했을 때 n-1번째 집은 x가 아닌 다른 두 색으로 칠할 수 있다.
이점을 이용하여 각 경우에 대하여(R,G,B로 칠한 경우) 최소가 되는 비용을 저장한다.
어려운 문제는 아니었으나 문제를 문제 그대로 받아들이지 못해서 헤매고 다른 사람의 풀이를 참고했다.
문제의 핵심을 파악하여 간단하게 생각하는 연습이 필요할 것 같다.
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):
#i번째를 빨간색으로 칠했을 때 최소 비용
cost[i][0] += min(cost[i-1][1], cost[i-1][2])
#i번째를 초록색으로 칠했을 때 최소 비용
cost[i][1] += min(cost[i-1][0], cost[i-1][2])
#i번째를 파란색으로 칠했을 때 최소 비용
cost[i][2] += min(cost[i-1][0], cost[i-1][1])
#마지막 집을 빨, 초, 파 각각 칠했을 때의 최소 비용을 모두 구하고 그 중에서 가장 최소가 되는 값으로 출력
print(min(cost[n-1]))
반응형
'알고리즘 > python' 카테고리의 다른 글
[python/파이썬] 백준 2447 별 찍기 - 10 (0) | 2022.09.02 |
---|---|
[python/파이썬] 백준 17478 재귀함수가 뭔가요? (0) | 2022.09.01 |
[python/파이썬] 백준 11568 민균이의 계략 (0) | 2022.07.28 |
[python/파이썬] 백준 10622 회의실 배정 3 (0) | 2022.07.27 |
[python/파이썬] 백준 20162 간식 파티 (0) | 2022.07.27 |