백준 | 1149 - RGB거리 (python)

🚦 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보다 작거나 같은 자연수이다.

 

출력

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

 

 

---

💡 해결방법

빨강, 초록, 파랑 색만 사용할 수 있으므로 2차원 배열을 사용해 총 3xn배열(n은 집의 수)을 만든다.

두번째 배열부터 반복문을 시작하여 첫번째 배열에서 현재 내 집 색의 비용을 제외한 나머지 색의 비용의 최솟값을 계속해서 더해준다.

 

26 40 83
49 60 57
13 89 99

 

위의 값이 입력값으로 들어온다면 d[1][0]에는 40과 83중 최솟값인 40이 두번째 배열의 첫번째 값인 49와 더해져 89값이 저장되는 것이다.

즉 점화식은 d[i][0] = min(d[i-1][1],d[i][2])+rgb[i][0] 이고 0, 1, 2일때 모두 숫자만 바꾸고 똑같이 적용된다.

d의 첫번째 배열에 각각 원본 값의 첫번째 배열 값을 넣어주고 반복문을 돌려주면 가장 마지막 배열은 각각 최솟값이 나오게 된다. 이 중 가장 최솟값을 출력시키면 된다.

 

👩🏻‍💻 소스코드

import sys
n = int(sys.stdin.readline())
rgb = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
d = [[0,0,0] for i in range(n)]
d[0][0] = rgb[0][0]
d[0][1] = rgb[0][1]
d[0][2] = rgb[0][2]

for i in range(1,n):
    d[i][0] = min(d[i - 1][1], d[i - 1][2]) + rgb[i][0]
    d[i][1] = min(d[i - 1][0], d[i - 1][2]) + rgb[i][1]
    d[i][2] = min(d[i - 1][0], d[i - 1][1]) + rgb[i][2]
    
print(min(d[n-1]))

 

 

---

 

1149번: RGB거리