백준 1149번 RGB거리

NameError·2021년 5월 3일

문제 링크

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

풀이 전 계획과 생각

이 문제는 처음 보면 굉장히 복잡해 보이는데 자세히 뜯어보면 간단한 동적 프로그래밍 문제로 이해할 수 있다.

1번 집의 색은 2번 집의 색과 같지 않아야 한다.
N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

이 말 때문에 상당히 헷갈릴 수 있는데 그냥 직전 집과는 다른 색으로 칠해야 한다는 뜻이다. 그리고 N번 집의 색은 N-1번 집의 색과 다르기만 하면 되고 1번 집과도 다를 필요는 없고.

그리고 한 가지 더 헷갈리는 요소는 각각의 집을 빨간색, 초록색, 파란색으로 칠하는 비용이 일정하게 정해져 있지 않고 각각의 집마다 다르게 배정되어 있다. 그래서 가장 싼 페인트를 가장 많이 사용하는 방향(?)으로 계산할 수 없고 각각의 집을 빨간색, 초록색, 파란색으로 칠하는 예상 비용을 모두 계산해야 한다.

현재 최솟값이 앞으로도 계속 최솟값은 아니다. 예를 들어 지금 집은 노란색으로 칠하는 게 제일 싼데 다음 집도 노란색으로 칠하는 게 제일 싸고 비용 차이도 훨씬 크다면 이번 집을 노란색으로 칠하고 직전 집을 칠하는 최소비용도 다른 색깔로 칠하는 경우 중에서 찾아봐야 할 수 있다.

따라서 현재의 집을 빨간색, 초록색, 파란색으로 칠하는 각각의 최소비용들을 모두 계산한 다음에 그것들 중에서 총 최소비용을 찾아야 한다.

풀이 (코드 블록 첨부)

# 백준 1149번 RGB거리 
import sys
N = int(sys.stdin.readline())
color_map=[list(map(int,list(sys.stdin.readline().split()))) for x in range(N)]
#print(color_map)
cost_map = [[0]*3 for x in range(N)]
#print(cost_map)
cost_map[0][0] = color_map[0][0] # 첫번째 집 빨간색으로 칠하는 비용
cost_map[0][1] = color_map[0][1] # 두번째 집 초록색으로 칠하는 비용 
cost_map[0][2] = color_map[0][2] # 세번째 집 파란색으로 칠하는 비용 
for i in range(1,len(color_map)):
    cost_map[i][0] = color_map[i][0] + min(cost_map[i-1][1],cost_map[i-1][2])
    # 현재 집 빨간색으로 칠하는 총비용 = 현재 빨간색 비용 + (직전 파란색 총비용과 직전 초록색 총비용 중 최솟값)
    cost_map[i][1] = color_map[i][1] + min(cost_map[i-1][0],cost_map[i-1][2])
    # 현재 집 초록색으로 칠하는 총비용 = 현재 초록색 비용 + (직전 빨간색 총비용, 직전 파란색 총비용 중 최솟 값)
    cost_map[i][2] = color_map[i][2] + min(cost_map[i-1][0],cost_map[i-1][1])
    # 현재 집 파란색으로 칠하는 총비용 = 현재 파란색 비용 + (직전 빨간색 총비용, 직전 초록색 총비용 중 최솟값)


print(min(cost_map[N-1]))    # 마지막 집 빨간색, 초록색, 파란색 총비용 중 최솟값