[solved.ac 실버1] 1149_RGB 거리 (파이썬, DP 풀이)

제한 사항

 

문제

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

출력

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

예제

---

나의 풀이

백트래킹 (시간 초과)

처음에 재귀 호출을 사용한 백트래킹으로 접근했다.

def rec_fun(r, ci, total):
    global answer
    if r == n:
        answer = min(answer, total)
        return
    for i in range(3):
        if i == ci: continue
        rec_fun(r + 1, i, total + costs[r][ci])


n = int(input())
costs = [list(map(int, input().split())) for _ in range(n)]
answer = 10 ** 9
for i in range(3):
    rec_fun(0, i, 0)
print(answer)

답은 맞게 나왔지만 문제의 제한 시간이 0.5초로 잡혀 있어서 시간 초과가 나왔다.

n이 최대 1,000이니까 최악의 상황에 대략 3 ^ 1,000 정도의 시간이 소요될 것이다.

 

이전에 비슷한 문제 유형을 DP로 풀이했던 기억이 나서 DP로 다시 시도하게 되었다.

 

DP 풀이 (성공)

DP는 기록하면서 풀이하는 방식이다. 이 문제에서 기록되는 것은 현재 위치(i)에서 R을 선택한 경우, G를 선택한 경우, B를 선택한 경우 이렇게 3가지 정보를 가지고 있다.

예를 들어 현재 위치(i)에서 R을 선택했을 때, 이전 위치(i-1)에서 G를 선택했을 때의 값과 B를 선택했을 때의 값 중 더 작은 값을 선택해서 현재 위치(i)의 R을 더한다.

G를 선택했을 때는 이전 위치의 R, B 중 더 작은 값, B를 선택했을 때는 이전 위치의 R, G 중 더 작은 값을 선택한 것이 된다.

리스트 인덱스는 0 ~ (n-1) 이다. n-1 위치까지 위 작업을 수행한 후 n-1 위치의 3가지 정보 중 가장 작은 값을 출력하면 된다.

n = int(input())
d = [list(map(int, input().split())) for _ in range(n)]
for i in range(1, n):
    d[i][0] += min(d[i - 1][1], d[i - 1][2])
    d[i][1] += min(d[i - 1][0], d[i - 1][2])
    d[i][2] += min(d[i - 1][0], d[i - 1][1])
print(min(d[n - 1][0], d[n - 1][1], d[n - 1][2]))

 

채점 결과