[백준/파이썬]1149 RGB거리

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

1149번: RGB거리

 

문제

백준 1149 RGB거리

N개의 집을 색칠할 때 드는 비용이 입력 값으로 준다.

 

그리고 양옆의 집들과는 색이 달라야 한다.

 

이때, 집을 색칠할때 발생하는 비용의 최솟값을 구하는 문제이다.

 

 

문제를 풀때 조금 헷갈렸다.

 

집이 3개가 있을 때,

 

1번 집을 칠하고

 

2번 집을 칠할 때 1번집을 칠할때 사용했던 색을 제외한 두 가지 색을 각각 칠하는 경우, 그리고 3번 집을 칠할때도 똑같이 2번 집을 칠한 색을 제외한 두가지 색을 또 각각 나눠서 모든 경우를 구한 후, 나오는 최솟값을 구해야 하는 것이 아닐까 라는 생각을 했었다.

 

그렇게 하기엔 시간제한이 0.5초 밖에 되지 않았고, 재귀 돌다가 프로그램이 멈춰버릴 것 같았다.

 

그래서 문제를 풀기 위해선 i번째 집을 빨간색, 초록색, 파란색 각각 어떤 색으로 시작할지 정해두고, i-1번째 집 중에서 i번째에서 칠하는 색이 아닌 나머지 두 색 중, 값이 더 적게 드는 색을 칠해주면 된다.

 

이를 점화식으로 쓰면

 

i = 1 ~ N

arr[i][빨간색] = min(arr[i-1][초록색], arr[i-1][파란색])

arr[i][초록색] = min(arr[i-1][빨간색], arr[i-1][파란색])

arr[i][파란색] = min(arr[i-1][빨간색], arr[i-1][초록색])

 

이렇게 다 돌고 나서

 

arr[-1]을 출력해 주면

 

2번째 집을

빨간색으로 시작했을때 최솟값

초록색으로 시작했을때 최솟값

파란색으로 시작했을때 최솟값

이 출력된다.

 

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

 

정답

 

n = int(input())
arr = []
for i in range(n) :
    arr.append(list(map(int,input().split())))

for i in range(1, n) :

    arr[i][0] += min(arr[i-1][1], arr[i-1][2])
    arr[i][1] += min(arr[i-1][0], arr[i-1][2])
    arr[i][2] += min(arr[i-1][0], arr[i-1][1])

print(min(arr[-1]))