[파이썬]백준 1149 RGB거리

링크

백준 1149 RGB거리

DP문제는 어렵다..

처음엔 백트래킹으로 가지치기를 수행할 수 있는 부분은 다 시행해줬음에도 시간초과로 풀지 못했다.

DP로 구현하니 풀 수 있었는데,
해당 문제의 핵심은 이전 집의 색만, 현재 집의 색에 영향을 준다는 점이다.
즉, 이번집을 빨간색으로 칠할 경우 이전집은 파란색으로 칠했거나 초록색으로 칠했어야 한다. 이를 코드로 구현하면 된다.

해당 집을 r,g,b로 칠했을 때 비용을 적을 memo(코드에선dp)를 2차원 배열로 만든다.

첫집은 자유롭게 칠할 수 있기 때문에 그냥 적어주고
그 다음집부턴 해당 집을 각각의 색으로 칠할 경우 이전 집이 가능한 색 중 작은 값에다가 칠할 색의 비용을 더해주면서 적어나가면 된다.

오답 코드 (백트래킹, 시간초과)

import sys; input = sys.stdin.readline

def bt(idx, total, previous):
    global min_cost
    if total > min_cost:
        return
    if idx == N:
        min_cost = total
        return
    else:
        for i in range(3):
            if i == previous: continue
            bt(idx + 1, total + cost[idx][i], i)

N = int(input())
cost = []
min_cost = 1000 * 1000
# idx 0빨 1초 2파
for _ in range(N):
    cost.append(list(map(int, input().split())))

bt(0, 0, -1)
print(min_cost)

정답 코드

import sys; input = sys.stdin.readline

N = int(input())
cost = [list(map(int, input().split())) for _ in range(N)]
# 해당 인덱스의 집을 r, g, b로 칠할때의 비용
dp = [[0, 0, 0] for _ in range(N)]
dp[0][0] = cost[0][0]
dp[0][1] = cost[0][1]
dp[0][2] = cost[0][2]

for i in range(1, N):
    # 빨간색으로 칠하는 경우, 이전이 초록이나 파랑이어야 함 두 경우를 비교
    # 두 경우중 값이 작은 것을 선택하고 그 값에 현재 집을 색칠하는 비용 누적
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[i][1]
    dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[i][2]

print(min(dp[N - 1]))

알게된 것👨‍💻

• DP는 어려워