오늘의 한 마디
어려운 문제를 쉬운 문제 여러개로 분해하는 것에 아직 익숙하지 않다...

• Baekjoon 문제 링크
• 현재 백준 문제집: 단기간 성장을 풀고 있습니다.

문제

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

출력

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

예제 입력 1

3
26 40 83
49 60 57
13 89 99

예제 출력 1

110

예제 입력 2

3
1 100 100
100 1 100
100 100 1

예제 출력 2

3

예제 입력 3

3
1 100 100
100 100 100
1 100 100

예제 출력 3

201

예제 입력 4

6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91

예제 출력 4

208

예제 입력 5

8
71 39 44
32 83 55
51 37 63
89 29 100
83 58 11
65 13 15
47 25 29
60 66 19

예제 출력 5

253

---

발상

보자마자 당연히 RGB거리 1 문제가 떠올랐다.

RGB거리 2 문제는, 한 가지 조건 빼고 RGB거리 1 문제와 정확히 일치한다.

RGB거리 1

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

RGB거리 2

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

RGB거리 2 문제에서는 "1번 집과 N번 집의 색도 달라야 한다"라는 조건이 추가되었다.

백준 #1149 RGB거리 1

# 다이나믹 프로그래밍
# 앞 집과 다른 색으로 칠해야...

import sys

N = int(sys.stdin.readline().rstrip())
houses = [[-1, -1, -1]]
for _ in range(N):
    houses.append(list(map(int, sys.stdin.readline().rstrip().split())))

R, G, B = 0, 1, 2

dp = [[-1] * 3 for _ in range(N+1)]
dp[1] = houses[1]

for i in range(2, N+1):
    dp[i][R] = min(dp[i-1][G], dp[i-1][B]) + houses[i][R]
    dp[i][G] = min(dp[i-1][R], dp[i-1][B]) + houses[i][G]
    dp[i][B] = min(dp[i-1][R], dp[i-1][G]) + houses[i][B]

print(min(dp[N]))

매우 간단한 dp 문제다.

하지만 1번 집과 N번 집의 색이 다르게 하려면 문제가 달라진다.

도대체 어디부터 시작하란 말인가?
집이 원형으로 배치되어 있다고 생각하면, 머리가 갈피를 못 잡고 빙빙 돈다.

1번 집을 R, G, B로 각각 시작하도록 고정하기

이 링크를 읽고 나서 빙빙 도는 머리가 멈출 수 있었다.

RGB거리 2 문제를 풀어내는 사고과정은 다음과 같다.

1. 1번 집을 반드시 R로 시작하도록 고정해놓을 수 없을까?
2. dp[1][G]와 dp[1][B] 값을 각각 INF로 설정하면 무조건 R에서 시작함을 보장할 수 있다.
3. 그렇게 한 뒤에 RGB거리 1 문제와 똑같이 돌린다.
4. dp[N][G]와 dp[N][B] 중에 최솟값을 얻으면, 1번 집이 R이면서, N번 집이 R이 아닌 경우의 RGB거리 최솟값을 얻을 수 있다!

그렇게 1번 집이 각각 R, G, B인 경우에 대해 RGB거리를 모두 구한 뒤, 그 중에 또 최솟값을 구하면 원하는 답을 얻어낼 수 있다.

---

풀이

import sys
INF = 1000*1000+1
R, G, B = 0, 1, 2

N = int(sys.stdin.readline().rstrip())
cost = [[-1, -1, -1]]
for _ in range(N):
    cost.append(list(map(int, sys.stdin.readline().rstrip().split())))

answer = INF
for color in [R,G,B]:
    dp = [[-1]*3 for _ in range(N+1)]

    dp[1] = [INF, INF, INF]
    dp[1][color] = cost[1][color]

    for i in range(2, N+1):
        dp[i][R] = min(dp[i-1][G], dp[i-1][B]) + cost[i][R]
        dp[i][G] = min(dp[i-1][R], dp[i-1][B]) + cost[i][G]
        dp[i][B] = min(dp[i-1][R], dp[i-1][G]) + cost[i][B]
    dp[N][color] = INF
    answer = min(answer, min(dp[N]))
print(answer)