[백준 17404 파이썬/python] RGB거리 2

RGB거리 2

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.5 초 (추가 시간 없음)	128 MB	10904	6318	5187	58.157%

1. 문제

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

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

• 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.

• N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.

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

2. 입력

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

3. 출력

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

4. 예제 입력 1

      

      

      

    
    

      <code />
    
3
26 40 83
49 60 57
13 89 99

5. 예제 입력 2

      

      

      

    
    

      <code />
    
3
1 100 100
100 1 100
100 100 1

6. 예제 입력 3

      

      

      

    
    

      <code />
    
3
1 100 100
100 100 100
1 100 100

7. 예제 입력 4

      

      

      

    
    

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

8. 예제 입력 5

      

      

      

    
    

      <code />
    
8
71 39 44
32 83 55
51 37 63
89 29 100
83 58 11
65 13 15
47 25 29
60 66 19

9. 예제 출력 1

      

      

      

    
    

      <code />
    
110

10. 예제 출력 2

      

      

      

    
    

      <code />
    
3

11. 예제 출력 3

      

      

      

    
    

      <code />
    
201

12. 예제 출력 4

      

      

      

    
    

      <code />
    
208

13. 예제 출력 5

      

      

      

    
    

      <code />
    
253

14. 풀이

      

      

      

    
    

      <code />
    
n = int(input())
a = [(0, 0, 0)] + [tuple(map(int, input().split())) for _ in range(n)]
d = [[0] * 3 for _ in range(n + 1)]
ans = 1000 * 1000 + 1
for k in range(3):  # house1's color
    for j in range(3):
        if j == k:
            d[1][j] = a[1][j]
        else:
            d[1][j] = 1000 * 1000 + 1
    for i in range(2, n + 1):
        d[i][0] = min(d[i - 1][1], d[i - 1][2]) + a[i][0]
        d[i][1] = min(d[i - 1][0], d[i - 1][2]) + a[i][1]
        d[i][2] = min(d[i - 1][0], d[i - 1][1]) + a[i][2]
    for j in range(3):
        if j == k:
            continue
        ans = min(ans, d[n][j])
print(ans)

Uploaded by N2T