[백준] 17404번 RGB 거리 2 - Python / 알고리즘 기초 1/2 - 다이나믹 프로그래밍 1 (도전)

ByungJik_Oh·2025년 4월 3일

Baekjoon Online Judge

[Baekjoon Online Judge]

목록 보기

67/244

💡 문제

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

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

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

입력

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

출력

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

💭 접근

1149번 RGB 거리 문제와 비슷하지만 조건이 하나 더 추가되었다. 바로 첫번째로 선택한 색과 마지막으로 선택한 색이 달라야한다는 것인데, 이 조건 하나로 문제가 많이 까다로워졌다.

비용의 최댓값이 1000이므로, 처음으로 선택할 색을 제외한 모든 색을 1001로 초기화 시킨다. 이렇게 되면 무조건 내가 선택하고자 하는 색만 선택할 수 있다.
두번째 ~ n-1번째 집은 이전에 선택한 색과 다른 최솟값을 선택한다.
마지막 n번째 집은 첫번째로 선택한 색과 달라야하므로, 최솟값이 될 수 없도록 첫번째에 선택한 색을 마찬가지로 1001로 초기화 시켜준다.

이를 테이블로 보자.
처음으로 선택한 집이 빨간색이라고 하였을 때,

i	R	G	B
0	26	1001	1001
1	49	60	57
2	1001	89	99

i	R	G	B
0	26	1001	1001
1	1050	86	83
2	1001	89	99

i	R	G	B
0	26	1001	1001
1	1050	86	83
2	1084	172	185

📒 코드

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
dp = [[] for _ in range(n)]

ans = []
for i in range(3):
    dp = [a[i][:] for i in range(n + 1)]
    dp[0] = [1001, 1001, 1001] # 선택하고자 하는 색을 제외하고 모두 1001
    dp[0][i] = a[0][i]
    dp[-1][i] = 1001 # 처음 선택한 색 1001

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

    ans.append(min(dp[-1]))

print(ans)