[백준] 1149번: RGB 거리 (python)

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

 

 

 

출력 :

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

 

 

 

 

풀이)

 

dp의 탑다운 풀이는 백트래킹과 많이 유사하다.

 

하지만 여기서 배열을 사용한 백트래킹은 dp를 적용하기 많이 까다롭기 때문에 

 

for문안의  if문 안에서 최대한 무리없이 진행되도록 해야한다.

 

이 문제의 조건은 결국 N번 집의 색은 N-1번 집의 색과 다르지 않아야 하고, 

 

이 조건은 2번집 부터 적용되므로,

 

if cur > 0 and prv == i:
    continue

 

를 적용할 수 있겠다.

 

이제 백트래킹을 이용한 풀이가 모두 완성되었으면, 이를 dp테이블에 담고 이를 출력해주면 

 

탑다운 형식의 dp코드가 완성된다.

 

import sys
sys.setrecursionlimit(1 << 30)
 
def recur(cur, prv):
    if cur == n:
        return 0
 
    # 방문한 적이 있다면 dp[cur][prv]를 리턴한다.
    if dp[cur][prv] != 100000:
        return dp[cur][prv]
 
    for i in range(0, 3):
        # 문제의 조건
        if cur > 0 and prv == i:
            continue
        # 여태까지 온 쌓아둔 dp와 현재 값 중 작은 것을 넣어준다.
        dp[cur][prv] = min(dp[cur][prv], recur(cur + 1, i) + li[cur][i])
 
    return dp[cur][prv]
 
 
n = int(input())
li = [list(map(int, input().split())) for i in range(n)]
dp = [[100000] * (n + 1) for i in range(n + 1)]
print(recur(0, 0))

 

---

출처 : https://www.acmicpc.net/problem/1149

1149번: RGB거리