백준 1149 파이썬 - RGB거리 - 동적 계획법

백준 1149 파이썬

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

1149번: RGB거리

이번 문제는 2차원 배열에서 앞뒤로 인덱스 번호가 다르게해서 합산한게 가장 적은 값을 구하는 문제이다.이런 최소나 최대값을 구하는 문제는 가장 먼저 동적 계획법이 떠오른다. 그런데... 만약... 가장 적은 비용만 저장하겠다는 생각에 중점을 두면... 아래와 같은 예외사항이 발생할 수 있다.

 

이전에 가장 적은 비용만 고려하면.... 위와 같이 비용이 같은 경우... 현재 집에서 이전에 어떤 색을 칠했는지... 구분해야하는 문제가 생깁니다. 그래서 현재 집에서 각각 색을 칠했을 때의 가장 적은 비용을 저장해서 재사용하는 것을 중점으로 둬야한다.

 

 

Python 풀이

import sys
read = sys.stdin.readline

N = int(read())
cache =[list(map(int, read().split())) for _ in range(N)]

for i in range(1, N):
    cache[i][0] += min(cache[i-1][1], cache[i-1][2])
    cache[i][1] += min(cache[i-1][0], cache[i-1][2])
    cache[i][2] += min(cache[i-1][0], cache[i-1][1])
print(min(cache[-1]))

• 주어지는 집과 색칠하는 비용을 미리 배열로 만들어 놓는다.
• 이전 집에 색칠했을 때의 최솟값을 갖고 오는데... 현재 색을 제외하고 나머지 두개의 색의 비용 중 최솟값을 갖고온다.
  • 이러면 집에서 각각 색을 칠했을 때의 최솟값이 배열로 저장된다.
• 마지막 열에서 가장 최솟값이 최종적으로 얻을 수 있는 최솟값이 된다.