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

문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog

 

1149번: RGB거리 문제 보러가기 

1149번: RGB거리

 

시간 제한: 0.5초 

메모리 제한: 128 MB

 

문제

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

3
26 40 83
49 60 57
13 89 99

 

예제 출력 1

96

 

예제 입력 5

6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91

 

예제 출력 5

208

 

 

---

 

대표적인 DP 문제 

import sys 
sys.stdin=open('input.txt', 'r')



if __name__=="__main__":
    N = int(input())
    dp = [list(map(int, input().split())) for _ in range(N)]
    
    for i in range(1,N):
        dp[i][0] += min(dp[i-1][1], dp[i-1][2])
        dp[i][1] += min(dp[i-1][0], dp[i-1][2])
        dp[i][2] += min(dp[i-1][0], dp[i-1][1])
    
    answer = min(dp[-1])
    print(answer)

 

 

참고:

https://zidarn87.tistory.com/272