Boj 1149 - [RGB 거리] (feat. Python)

[RGB 거리]

1149번: RGB거리

 

문제 접근

• 두 가지 경우의 수 확인
  • 첫 번째, 두 번째, 세 번째 집의 색이 전부 다를 경우 => O O O
  • 두 번째 집만 다를 경우 => O O O
• 위 두 경우의 수를 구하기 위한 점화식 구하기
  • N번 째 선택한 색깔이 빨강일 경우
  •  N-1번 째 선택한 색깔이 초록일 경우와 파랑일 경우 중에 더 작은 값을 빨강의 값과 더해준다
  • 위 두 과정을 반복하는 점화식을 세우면
    • RED[N] = min(GREEN[N-1], BLUE[N-1]) + red_value
    • 해당 점화식은 초록과 파랑에 대해서도 점화식을 구해줘야 한다

 

Code

n = int(input())

rgb = [[0]*3 for _ in range(n)]

for i in range(n):
    r, g, b = map(int, input().split())
    rgb[i][0] = r
    rgb[i][1] = g
    rgb[i][2] = b

#print(*rgb, sep='\n')

INF = 1e9

red = [INF] * n
green = [INF] * n
blue = [INF] * n

red[0] = rgb[0][0]
green[0] = rgb[0][1]
blue[0] = rgb[0][2]

for i in range(1, n):
    red[i] = min(green[i-1], blue[i-1]) + rgb[i][0]
    green[i] = min(red[i - 1], blue[i - 1]) + rgb[i][1]
    blue[i] = min(green[i - 1], red[i - 1]) + rgb[i][2]

results = [red[n-1], green[n-1], blue[n-1]]

print(min(results))