[Python: DP] BOJ1149 - RGB거리

문제

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

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

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

---

입력

3
26 40 83
49 60 57
13 89 99

출력

96

---

원래 dp 새로운 배열을 만들어서 넣어야 하지만 입력 배열에 덮어써주면 메모리를 많이 사용할 필요 없을 것 같다.

조건이 굉장히 길지만 인접한 것이 다르면 된다는 조건이다. RR, BB, GG 이렇게 연속으로 나오면 안된다는 것이다. 

처음에 색깔(빨간색, 초록색, 파란색)을 선택하면 나머지 값 중 최소 값을 선택하는 경우를 따져보면 된다.

 

역순으로 담아가면서 소스코드를 작성해보자

 

https://penglog.tistory.com/60

[C++] 백준 BOJ 1149 RGB 거리

https://peisea0830.tistory.com/7

[Python 3] BOJ - 1149 "RGB 거리"

소스코드

import sys
dp = []
n = int(input())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

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

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

 

스터디원이 좋은 꿀팁을 알려주셨다. n-1에서 n으로 어떻게 가야할지 생각하면 DP 문제에 점화식과 소스코드를 잘 작성할 수 있다고 한다. 스터디가 끝나면 DP 문제부터 많이 풀어봐야겠다.