[BOJ] 17404 RGB거리 2

date

Aug 5, 2023

slug

boj-17404

author

status

Public

문제 링크

https://www.acmicpc.net/problem/17404

문제

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

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

1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.

N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.

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

문제풀이

문제 : RGB 거리 1 에서 마지막 조건 하나가 추가된 문제이다.

RGB 거리 1 문제의 핵심은 N번째 집이 특정한 색으로 색칠됬을 경우에 N-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]

여기에 마지막집은 첫번째 색과 같으면 안되는 조건이 붙었는데

마지막 집이 어떤 색으로 칠해야 조건에 부합되는지를 알기 위해서는 첫번째 집을 고정 시키는 작업이 필요하다.

그러므로 첫번째 집을 빨간색으로 고정하고

dp[0] = [inf, inf, inf] # 모두 선택되지 않게끔

dp[0][c] = cost[0][c] # 빨간색만 선택되게끔

DP sequence는 rgb 거리1과 동일하게 진행하면서

마지막에 dp[N-1]의 빨간색을 inf로

why? 첫번째집과 마지막 집은 색이 무조건 달라야함

그리고 ans에 파란색과 초록색의 DP중 최소값을 min에 넣어준다.

이를 초록집과 파란색집에 대해서 반복해주면 조건을 만족하면서 문제의 해를 구할 수 있다.

파이썬 문제풀이 코드


import sys
input = sys.stdin.readline

N = int(input())

inf = ans = 1e9

cost = []

for _ in range(N):
    cost.append(list(map(int, input().split()))) # RGB 거리 넣어주기

for c in range(3):    
    dp = [[0] * 3 for _ in range(N)]
    
    dp[0] = [inf, inf, inf]
    dp[0][c] = cost[0][c] 
    
    for i in range(1, N):
        dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0]
        dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[i][1]
        dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[i][2]
    
    dp[N-1][c] = inf
    ans = min(ans, min(dp[N-1]))
    
print(ans)

시간복잡도

O(N^2)

입력

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

출력

예제 입력

예제 출력

알고리즘 분류

다이나믹 프로그래밍