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

DP 유형에 속하는 여러 문제들을 풀어보고자 해당 문제를 골랐다.

 

N개의 집을 각각 빨강, 초록, 파랑 색으로 칠하는 비용이 각각 입력된다.

그런데 i번째 집은 i-1과 i+1번째에 해당하는 집들은 같은 색을 선택할 수 없다.

즉, 연속하는 2개의 집은 같은 색일 수 없다는 것이다.

 

1149번 RGB거리 풀이

[시도1]  맞았습니다!! with 솔루션

N = int(input())

color = []

for _ in range(N):
  rgb = list(map(int, input().split()))
  color.append(rgb)

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

print(min(color[N-1][0],color[N-1][1],color[N-1][2]))

color 리스트에 각 집의 rgb 색상 비용을 리스트로 넣는다.

색상이 3개로 한정되어 있으므로

1. i번째 집이 빨강이므로 i-1번째집이 초록인 경우와 파랑인 경우 중에서 최솟값 + i번째 빨강집 비용

2. i번째 집이 초록이므로 i-1번째 집이 빨강인 경우와 파랑인 경우 중에서 최솟값 + i번째 초록집 비용

3. i번째 집이 파랑이므로 i-1번째 집이 초록인 경우와 빨강인 경우 중에서 최솟값 + i번째 파랑집 비용

1, 2, 3번은 for문 안에 코드로 표현된다.

주의할 점은 i번째 집에 대해서 i-1번째 집의 최솟값을 찾기 때문에 for문의 시작값은 0이 될 수 없다.

최종적으로 N번째 집이 (color 리스트를 0부터 채웠으므로 N-1 인덱스) 빨강일 경우, 초록일 경우, 파랑일 경우 중에 최소값을 구하면 for문을 통해서 N번째 집의 앞에 있는 집들의 색도 총합이 최솟값이 되도록 정해진다.

 

 

 

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

1149번: RGB거리