문제
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보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
첫번째 접근 방법
- 재귀함수로 접근
- i번째 집의 색깔을 제외한 나머지 색깔을 i+1번째 색깔로 하여 재귀호출
- 선택한 값들 중에 최솟값을 반환
N = int(input())
houses = []
for _ in range(N):
houses.append(list(map(int, input().split())))
def rec(num, cost, color):
if num < N-1:
num += 1
if color == 'R':
return min(rec(num, cost+houses[num][2], 'B'), rec(num, cost+houses[num][1], 'G'))
elif color == 'G':
return min(rec(num, cost+houses[num][0], 'R'), rec(num, cost+houses[num][2], 'B'))
else:
return min(rec(num, cost+houses[num][0], 'R'), rec(num, cost+houses[num][1], 'G'))
else:
return cost
print(min(rec(0, houses[0][0], 'R'), rec(0, houses[0][1], 'G'), rec(0, houses[0][2], 'B')))
어쩐지 문제가 쉽게 풀린다 했더니 아니나 다를까 역시 시간초과였다.
재귀함수를 호출하는데에 시간이 소요되기 때문에 재귀가 아닌 다른 방식으로 접근해보기로 했다.
이번에는 DP로 접근해보았다.
점화식을 세워 각각 i 번째 집을 칠하기 위해 가능한 최소값을 구해나가는 것이다.
색은 모두 3가지이므로 각각의 집마다 각각의 색으로 칠할 때에 드는 비용을 모두 계산해주었다.
점화식
dp[i][빨강] = 최소값(dp[i-1][초록, 파랑]) + 현재 색깔의 비용
dp[i][초록] = 최소값(dp[i-1][빨강, 파랑]) + 현재 색깔의 비용
dp[i][파랑] = 최소값(dp[i-1][빨강, 초록]) + 현재 색깔의 비용
코드로 구현 해보았을 때, 다음과 같았다.
# 3가지 색이므로 3종류의 색 모두 구함
for i in range(1, N):
# 현재 집의 색깔별 가격은 이전 집의 현재색을 제외한 나머지 색의 최소 + 현재 색의 가격
dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + houses[i][0]
dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + houses[i][1]
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + houses[i][2]전체 코드
N = int(input())
houses = []
# 각 집 별 색깔들 비용 리스트에 추가
for _ in range(N):
houses.append(list(map(int, input().split())))
# 점화식
# i번째 집을 각각의 색으로 칠할때의 가격
# i-1번째 집을 현재색을 제외한 나머지 색으로 칠한 가격중 최소 + 현재 색의 가격
# 3가지 색이므로 i번째마다 3종류의 색을 칠하는 가격을 모두 구한다
dp = [[0]*3 for i in range(N)]
# 첫번째 집은 색깔의 비용 그대로 지불하면 됨
dp[0] = houses[0]
# 3가지 색이므로 3종류의 색 모두 구함
for i in range(1, N):
# 현재 집의 색깔별 가격은 이전 집의 현재색을 제외한 나머지 색의 최소 + 현재 색의 가격
dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + houses[i][0]
dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + houses[i][1]
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + houses[i][2]
# N번째까지 모두 칠했을 때의 가격 중 최소값 출력
print(min(dp[-1]))아직까지는 DP 알고리즘이 익숙치 않아서 문제를 푸는데에 시간이 생각보다 많이 걸렸고, 검색을 하면서 여러가지 힌트를 얻음으로써 풀 수 있었다.
