[알고리즘][파이썬]1149-RGB거리

 

 

문제

 

코드

import sys
n = int(sys.stdin.readline())
R=[]
for i in range(n):
    r,g,b = map(int,sys.stdin.readline().strip().split()) #strip왼쪽 공백 제거

    if(i==0):
        RGB=[r,g,b]
        continue
    RGB = [min(RGB[1], RGB[2]) + r, 
           min(RGB[0], RGB[2]) + g,
           min(RGB[0], RGB[1]) + b]
    
print(min(RGB))

 

집을 빨강,초록,파랑 중 하나의 색으로 칠해야하는데

이때 집마다 빨강,초록,파랑색을 칠하는 비용이 제공된다.

 

i번째 집은 i+1번째 집과 색이 무조건 달라야하는 것이 특징이다.

이 문제는 DP로 풀이가 가능하다.

 

풀이방법

 

1번째 집(i==0) : red,green,blue 비용을 RGB배열에 순서대로 저장을 한다.

 

2번째 집(i==1):

칠하려는 색의 비용과 이전 집의 비용이 들어있는 RGB배열에서

해당 색을 제외한 색 중 최소비용을 합쳐서 RGB배열에 순서대로 넣는다.

 

그 이후 집(i>1):

칠할려는 색의 비용과 이전에 계산된 값이 들어있는 RGB배열에서

해당 색을 제외한 색 중 최소비용을 합쳐서 RGB배열에 순서대로 넣는다.

 

for문이 끝나면 이전 집과 색이 겹치지 않은 상태에서 나올 수 있는 최소비용 결과가 각 자리(r,g,b)별로 나온다.

이 세가지 경우 중 가장 작은 비용이 최종 최소비용이라고 할 수 있다.

 

DP(다이나믹 프로그래밍)
#동적계획법
#모든 작은 문제들을 한번만 푼다.
#작은 문제의 계산값을 저장해서 다음 상위 문제의 계산에 사용한다.(상향식 접근법)
#조건:
부분반복문제 ->ex)피보나치수열
최적 부분 구조 ->ex)작은 부분에서 구한 최적의 답으로 상위 문제의 최적의 답을 구할 수 있는 문제