문제 (백준 1149번 RGB거리)
출처 : https://www.acmicpc.net/problem/1149
문제 이해
조건:
- RGB거리에 있는 N개의 집들은 일렬로 나열되어있다.
- 집은 R(빨강), G(초록), B(파랑) 중 하나의 색으로 칠한다.
- 서로 이웃한 집끼리는 색이 같으면 안된다.
- 각 집의 색을 칠하는데 색마다 가격이 다르다.
구해야할 것:
- 위 조건을 만족하면서 모든 집을 칠했을때 비용의 최솟값을 구하면 된다!
문제 접근
이 문제를 보니 시간도 상당히 짧고 이웃한 집끼리의 관계를 드러낸 것으로 보아 dp의 냄새가 많이 나죠? ㅎㅎ
한번 점화식을 구해보겠습니다.
단순하게 보면 n번째집의 색을 n - 1의 집의 색과 다르면서 가격이 최소인 색을 n의 집에 칠하기만 한다면 될 것 같습니다. 하지만 이는 오답을 도출해냅니다.
반례를 들어보겠습니다.
위의 RGB 가격 표를 참고해보겠습니다.
n = 1인경우 최솟값은 1로 1번집에는 R을 칠하고 비용은 1이 됩니다.
n = 2인경우 최솟값은 1이지만 1번집에 이미R이 칠해져있기 때문에 2번집에는 G를 칠하고 최소비용은 100이됩니다.
n = 3인경우 최솟값은 20이지만 2번집에 G가 칠해져 있기 때문에 3번집에는 R을 칠하고 최소비용은 100이 됩니다.
결과적으로 색을 칠하는데 비용은 201 입니다.
하지만!!
최소비용은 1번집에 G(비용100), 2번집에 R(비용1), 3번집에 G(비용20)를 칠했을 경우로 비용은 121입니다.
그렇다면 어떻게 구할 수 있을까요??
dp라는 배열을 만들어 색깔의 갯수가 3개이므로 길이가 3인 배열을 저장하는 2차원 배열을 만들어 계산합니다.
3가지의 경우로 나누어 살펴보겠습니다
-
2번째 집에 R을 칠했다면
1번째 집은 G나 B를 칠할 수 있습니다. 이를 식으로 표현하면
dp[2][0] = min(dp[1][1], dp[1][2]) + price[2][0] -
2번째 집에 G를 칠했다면
1번째 집은 R이나 B를 칠할 수 있습니다. 이를 식으로 표현하면
dp[2][1] = min(dp[1][0], dp[1][2]) + price[2][1] -
2번째 집에 B를 칠했다면
1번째 집은 R이나 G를 칠할 수 있습니다. 이를 식으로 표현하면
dp[2][2] = min(dp[1][0], dp[1][1]) + price[2][2]
어느정도 점화식의 규칙이 보이죠??
점화식:
dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + price[i][0]
dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + price[i][1]
dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + price[i][2]
입니다.
코드
import sys
input = sys.stdin.readline
# n: 집의 개수
n = int(input().strip())
price = [[0, 0, 0]]
for _ in range(n):
# R, G, B의 비용 순서대로
price.append(list(map(int, input().strip().split())))
dp = [[0] * 3 for _ in range(n + 1)]
def sol():
for i in range(1, n + 1):
# i번째 집에 R을 칠한 경우의 최소비용
dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + price[i][0]
# i번째 집에 G을 칠한 경우의 최소비용
dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + price[i][1]
# i번째 집에 B을 칠한 경우의 최소비용
dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + price[i][2]
sol()
print(min(dp[n]))후기
처음에는 백트래킹으로 최솟값을 구하려 했으나 dp였습니다... 후후.. 아직 제가 부족하다는 것이겠죠! 이 문제를 풀면서 dp는 1차원배열만 생각했었는데 2차원배열로도 풀 수 있다는것을 보니 1차원 배열에만 국한된 사고가 편협한 사고였음을 느끼게 되었습니다!
