문제 링크
https://www.acmicpc.net/problem/1149
문제 유형
DP (다이나믹 프로그래밍)
🌈문제
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
1번 집의 색은 2번 집의 색과 같지 않아야 한다.
N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
입력
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
1. 아이디어
이 문제를 보자마자 그림을 막막 그렸고 그려다 보니까 딱 감이 왔다..!
위 그림과 같이 점화식을 세워야겠군...이라는 생각이 들었고, 어떤 점화식을 세울지 고민을 하던 중 번뜩! 떠오르는 아이디어가 있었다.
바로 아래의 식이다.
if j == 0:
d[i][0] = min(d[i] + RGB[i+1][j+1], d[i] + RGB[i+1][j+2])
elif j == 1:
d[i][1] = min(d[i]+RGB[i+1][j-1], d[i]+RGB[i+1][j+1])
else:
d[i][2] = min(d[i]+RGB[i+1][j-1], d[i]+RGB[i+1][j-2])d라는 배열에 각 색에 대한 정보를 부여한다. 그리고 각 집에 대한 색의 비용을 저장한 RGB라는 배열을 다음과 같이 정의하는 것이다. i개의 집까지의 최적의 비용으로 정의한 것!!
즉 d[i]의 의미는 i개의 집까지 왔을 때, 즉 i번째 집의 페인트를 칠하는 최적의 비용이다.
이를 d라는 배열에 저장해 두고, 다음 집을 칠할 때 이 최적의 수를 계속하여 사용하는 것을 min함수로 수행할 수 있게끔 해 주는 것이다.
2. 코드 작성
구현하는 데 조금 어려움이 있었다. ㅠㅠ 역시 알골 공부를 하면서 내 머릿속에 있는 생각을 논리적으로 저장 및 코드로 구현하는 데 많은 노력과 공부를 해야겠다고 깨닫는 하루였다.
N = int(input())
RGB = []
for _ in range(N):
RGB.append(list(map(int, input().split())))
# 각 집에 대한 정보를 이차원 배열로 저장
#d[i]는 i번째 집까지의 최적의 색칠 비용이다.
d=[[0,0,0] for i in range(N)]
d[0] = RGB[0]
for i in range(1,N): #[i는 0번집, 1번집, 2번집 계산]
d[i][0] = min(d[i-1][1]+ RGB[i][0], d[i-1][2] + RGB[i][0])
d[i][1] = min(d[i-1][0]+RGB[i][1], d[i-1][2]+RGB[i][1])
d[i][2] = min(d[i-1][1]+RGB[i][2], d[i-1][0]+RGB[i][2])
print(min(d[-1]))
i번째까지 최적의 합은 i에 저장된다.
선택 기준을 내가 현재 칠한 색은 무엇인가?로 두고, 내가 현재 n번째 집에서 칠한 색이 빨간색[0], 초록색[1], 파란색[2]일때를 기준이다. 그 전에 색칠한 집의 최소를 골라, 현재 색으로 다시 집어넣어 DP로 구현하는 것이다.
