다이나믹 프로그래밍 기초 문제들을 푸는 중 이 문제에서 꽤 오래 막혀있었다. 혼자서 이리저리 고민하다 결국 해결방법이 떠오르지 않아 인터넷에서 풀이를 확인했다. 며칠간 골머리를 앓게 만든 문제는 너무 간단하게 풀렸다.
문제내용
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보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
고민과정
처음 접근할 때 맨 땅에 헤딩하는 느낌이었다. 모든 집을 칠하는 최소 가격은 어찌됐든 각 집의 색칠 가격 중 최소인 것들과 연관이 있을 것이라 생각해서 일단 각 집을 R,G,B로 칠하는 가격 중에서 최소인 것들을 배열에 저장했었다.
이 최소인 인덱스들 중 이웃한 집과 칠한 색이 겹치는 부분만 수정하면 답을 구할 수 있지 않을까 하고 생각했다. 그래서 1부터 n-1까지 인덱스를 증가시키며 최소 가격인 색(R,G,B를 각각 0, 1, 2로 나타냈다.)이 동일한 경우를 발견하면 같은 색으로 칠해진 2개의 집의 선택되지 않은 색 중 가장 가격이 싼 색으로 두 집 중 하나를 변경시켜봤다. 예시 입력에 대해 올바른 출력을 내는 걸 확인하고 제출했더니 1퍼센트로 못 찍고 틀려버렸다.
이후에 입력 N을 분할하며 해결하거나, 이런저런 조건문을 추가해봤지만 코드만 복잡해질 뿐 채점결과는 그대로였다.
해결방법은 지금까지 내가 고민했던 방식과 거리가 멀었다. 최솟값을 이용한다는 점은 동일했지만, 나는 각 집에 칠해진 색을 의미하는 인덱스 자체를 조정하며 연산하는 과정을 너무 복잡하게 만들어버렸다.
해결
이 문제의 해결방법에서 3 x n 크기의 배열을 이용하여 최소 비용을 지속적으로 갱신해나간다. 이 방법은 i(1<= i <= n-1)번째 집을 칠할 비용을 구할때 이전 집들에 대해 어떤 색을 칠할지 계산하는 과정을 생략하게 해준다. i번째 집을 R로 칠할때는 i-1번째 집을 G, B로 칠했을 때만 가능하며, 이 중 최소비용인 것에 더한다. 동일한 방법으로 B를 칠할 경우 R, G이고, G를 칠할 때는 R, B 중 최솟값에 해당 색상 가격을 더한다. 이렇게 하면 i번째 집을 R, G, B로 각각 칠할때 최소비용이 모두 저장되게 된다.
테이블을 이용한 이런 방식은 주식 사고 팔기 문제를 해결할 때 본 기억이 있다. 하지만 고려할 자료가 많아지고, 한 번 비효율적인 방식에 빠져버리게 되니 쉽게 기존 방식을 버리는 것이 쉽지 않았다. DP 문제의 핵심은 이전에 해결한 문제를 쉽게 해결하는 것인데도 말이다. 이해와 경험의 부족이 빗어낸 결과라 생각한다.
다음은 제출한 코드이다. 이 알고리즘은 O(N)의 공간복잡도와 O(N)의 시간복잡도를 보인다.
# 국경의 긴 터널을 빠져나오자, 눈의 고장이었다. 밤의 밑바닥이 하얘졌다. 신호소에 기차가 멈춰섰다.
def solve() :
n = int(input())
houses = []
for i in range(0, n) :
houses.append(list(map(lambda x : int(x), input().split())))
costs = [[houses[0][0], houses[0][1], houses[0][2]]]
for i in range(1, n) :
costs.append([houses[i][0], houses[i][1], houses[i][2]])
costs[i][0] = costs[i][0] + min(costs[i-1][1], costs[i-1][2])
costs[i][1] = costs[i][1] + min(costs[i-1][0], costs[i-1][2])
costs[i][2] = costs[i][2] + min(costs[i-1][0], costs[i-1][1])
print(min(min(costs[n-1][0], costs[n-1][1]),costs[n-1][2]))
solve()