백준 1149번: RGB거리

백준 1149번: RGB거리

아이디어

i번째 집을 R, G, B로 칠하는 경우, i-1번째 집까지 최소의 비용으로 칠하는 방법은 정해져있다. 이를 배열에 기록하고 다음 계산때 활용해야 한다.

입력이 다음과 같다고 하자.
이때 1번째 집을 R로 칠하려면, 0번째 집이 G와 B로 칠해진 경우 중 더 비용이 적은 경우를 택해야 한다. 0번째 집의 G로 칠하는 비용이 더 적으므로, 1번째 집을 R로 칠하려면 0번째 집을 G로 칠해야 한다.

점화식으로 표현해보면
최소비용[i][R] = min(최소비용[i-1][G], 최소비용[i-1][B]) + 비용[i][R]
이고 다음과 같은 결과를 얻을 수 있다.

코드

T = int(input())
rgb = [list(map(int, input().split())) for _ in range(T)]
rgbStreet = [[0] * 3 for _ in range(T)]

rgbStreet[0] = rgb[0]

for i in range(1, T):
    # 0: Red, 1: Green, 2: Blue
    rgbStreet[i][0] = min(rgbStreet[i-1][1], rgbStreet[i-1][2]) + rgb[i][0]
    rgbStreet[i][1] = min(rgbStreet[i-1][0], rgbStreet[i-1][2]) + rgb[i][1]
    rgbStreet[i][2] = min(rgbStreet[i-1][0], rgbStreet[i-1][1]) + rgb[i][2]

print(min(rgbStreet[T-1]))

여담

열심히 재귀함수로 풀었는데 시간초과가 나버렸다.
다음부터는 무지성 완전탐색을 자제해야겠다.

def solve(houseIndex, cost):
    # 기저 사례: 모든 집을 다 칠한 경우
    if len(rgbStreet) == len(rgbList):
        return cost
    else:
        ret = INF
        for i in range(3):
            # 비어있으면 아무거나 칠하고
            if not rgbStreet:
                pass
            # 바로 직전 집에 칠해진 색은 칠하지 않는다.
            elif rgbStreet[-1] == i:
                continue
            rgbStreet.append(i)
            ret = min(ret, solve(houseIndex+1, cost + rgbList[houseIndex+1][i]))
            rgbStreet.pop()
        return ret


rgbStreet = []
INF = 987654321

T = int(input())
rgbList = [list(map(int, input().split())) for _ in range(T)]
print(solve(-1, 0))