백준 - 1149- RGB거리 - Python/다이나믹 프로그래밍

1149번: RGB거리 (acmicpc.net)

1149번: RGB거리

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

 

풀이1

 

이것도 문제 자체를 이해 못하겠음 ㅡㅡ 코드보고 이해가 빠름

첫번째는 계산하지 않고 두번째 부터 시작해서 빨, 그, 블 경우를 계산하는데 그 이전의 값들 중 같은 색을 제외한 min을 더해주는 것을 반복한다. 결국 빨강, 초록, 파랑집을 선택한 모든 경우에 대해 최솟값만 더해져 나오게 되며 그중에서 최솟값을 선택하면 된다. 

 

import sys
input=sys.stdin.readline

n=int(input())
RGB=[]

for i in range(n):
    RGB.append(list(map(int,input().strip().split())))

for i in range(1,n):
    #빨간집
    RGB[i][0]=min(RGB[i-1][1],RGB[i-1][2])+RGB[i][0]
    #초록집
    RGB[i][1]=min(RGB[i-1][0],RGB[i-1][2])+RGB[i][1]
    #파란집
    RGB[i][2]=min(RGB[i-1][0],RGB[i-1][1])+RGB[i][2]

print(min(RGB[n-1]))

풀이2

import sys
# 집의 수
n = int(sys.stdin.readline())
rgb_pay = [[0] * 3 for i in range(n)]
 
for i in range(n):
    # 각 색별 페인트 비용
    rgb_pay[i][0], rgb_pay[i][1], rgb_pay[i][2] = map(int, sys.stdin.readline().split())
 
#이번에 빨강,초록,파랑을 골랐을때의 최솟값이 들어간다.0=빨강 1=초록 2=파랑
rgb_sum = [[0] * 3 for i in range(n)]
 
for i in range(n):
    if i == 0:
        rgb_sum[i] = rgb_pay[i]
 
    else:
        # 이번에 빨강을 고를때 최솟값(파랑,초록 둘중 작은거)
# 이번에 초록을 고를때 이전값들중에서 최솟값(빨강,파랑)
# 이번에 파랑을 고를때 이전값들중에서 최솟값(빨강,초록)
        rgb_sum[i][0] = rgb_pay[i][0] + min(rgb_sum[i - 1][1], rgb_sum[i - 1][2])
        rgb_sum[i][1] = rgb_pay[i][1] + min(rgb_sum[i - 1][0], rgb_sum[i - 1][2])
        rgb_sum[i][2] = rgb_pay[i][2] + min(rgb_sum[i - 1][0], rgb_sum[i - 1][1])
 
 
print(min(rgb_sum[n - 1]))    #최종적으로 빨강,파랑,초록 을 골랐을때 최솟값

사용된 개념

velog.io/@gillog/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming

동적 계획법(Dynamic Programming)