백준 1149 파이썬(DP)

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

1149번: RGB거리

DP문제를 계속해서 풀면서 느끼는점은

결국 점화식을 생각해내는 것이 핵심 포인트인것 같다.

문제를 어떻게 쪼개고 반복해서 연산한다음 합칠것인지 충분히 고민하고 문제를 푸는게 오히려 더 빠르고 정확하다는 생각이 든다.

 

• 점화식

i번째에 빨강을 칠할 때 최소값 = i번째 빨강의 비용 + min(i-1번째 파랑의 최소값, i-1번째 초록의 최소값)

 

• 코드

# 1149 - RGB거리 
# i 번째 빨강의 최소값 = i번째 빨강의 비용 + min(i-1번째 파랑의 최소값, i-1번째 초록의 최소값)
# 이런 아이디어이다. 결국 dp를 이용한 점화식을 생각해내는것이 중요 포인트이다.

import sys
input = sys.stdin.readline

t = int(input())
rgb = []
for _ in range(t):
    rgb.append(list(map(int,input().split())))

rgb_min = [[0,0,0] for _ in range(t)]

# rgb_min리스트의 초기값 설정
rgb_min[0][0] = rgb[0][0] # 첫번째 빨강 비용
rgb_min[0][1] = rgb[0][1] # 첫번째 초록 비용
rgb_min[0][2] = rgb[0][2] # 첫번째 파랑 비용


for i in range(1,t):
    rgb_min[i][0] = rgb[i][0] + min(rgb_min[i-1][1], rgb_min[i-1][2]) #i번째 빨강을 칠할때 최소값
    rgb_min[i][1] = rgb[i][1] + min(rgb_min[i-1][0], rgb_min[i-1][2]) #i번째 초록을 칠할때 최소값
    rgb_min[i][2] = rgb[i][2] + min(rgb_min[i-1][0], rgb_min[i-1][1]) #i번째 파랑을 칠할때 최소값

print(min(rgb_min[t-1]))