[백준 17404 🥇] RGB 거리2

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

17404번: RGB거리 2

문제

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

출력

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

 

import sys
from collections import deque

n=int(sys.stdin.readline())
# 빨강 초록 파랑 칠하는 비용
cost=[list(map(int, sys.stdin.readline().split(' '))) for _ in range(n)]

# 시간초과 코드(bfs)
# 1번 집을 빨, 초, 파로 칠하는 경우
# 빨=0, 초=1, 파=2
# minvalue=1e9
# for one in range(3):
#     # 컬러 값과 비용과 인덱스 저장
#     queue=deque()
#     queue.append((one, cost[0][one], 0))
#     while queue:
#         cur_color, cur_cost, cur_idx =queue.popleft()
#         if cur_idx==n-1:
#             minvalue=min(cur_cost, minvalue)
#         elif cur_idx==n-2:
#             for new_color in range(3):
#                 if new_color!=one and new_color!=cur_color:
#                     queue.append((new_color, cur_cost+cost[cur_idx+1][new_color], cur_idx+1))
#         else:
#             for new_color in range(3):
#                 if new_color!=cur_color:
#                     queue.append((new_color, cur_cost+cost[cur_idx+1][new_color], cur_idx+1))
#
# print(minvalue)

# dp를 이용해서 풀어보자
# 빨=0, 초=1, 파=2
ans=1e9
for i in range(3):
    dp=[[1e9, 1e9, 1e9] for _ in range(n)]
    dp[0][i]=cost[0][i]
    for j in range(1, n):
        dp[j][0]=cost[j][0]+min(dp[j-1][1], dp[j-1][2])
        dp[j][1]=cost[j][1]+min(dp[j-1][0], dp[j-1][2])
        dp[j][2]=cost[j][2]+min(dp[j-1][0], dp[j-1][1])
    for c in range(3):
        if c!=i:
            ans=min(ans, dp[n-1][c])

print(ans)

처음에 BFS로 풀기를 시도했다가 시간초과가 발생했다..! 집의 개수 N이 최대 1000개인데, 모든 경우의 수를 다 탐색하려면 시간초과가 날 수 밖에 없긴 했다. 

 

그래서 DP를 이용해서 풀어보기로 했다! 처음에 DP로 접근하는 방식이 어려워서 헤맸다.

 

우선 dp 배열에 첫번째 집을 빨강(0), 초록(1), 파랑(2)으로 설정하는 경우를 for문을 이용해서 반복하면서 탐색해주고, 첫 번째 집을 각각의 색으로 설정한 상태에서 i번째 집을 빨강, 초록, 파랑으로 설정하는 경우 각각의 최소 비용을 저장하기 위해서 dp[n][3] 크기의 1e9로 초기화된 배열로 선언했다.

 

그리고, 2번째 집부터 n번째 집까지 탐색을 해준다. 

dp[j][0]은 j번째 집에 빨강색을 칠했을 때의 최소 비용을 구하는 것이다. 우선, cost[j][0]에 저장된 비용에 j-1번째 집에 초록색을 칠하거나, 파랑색을 칠하는 비용 중 더 작은 값을 더해서 dp[j][0]에 저장한다. 

j를 1에서 n-1까지 반복하면서 dp[][] 배열에 최소 비용을 저장한다. 

 

그리고, 가장 바깥 for문 즉, 첫번째 집에 어떤 색을 칠할 것인지 반복하는 for문이 끝날 때마다 첫번째 색과 다른 색이 칠해진 dp[n-1][c]의 값 중 최소값으로 ans를 갱신한다.