[백준/Python] 1149. RGB 거리

https://www.acmicpc.net/problem/1149

 

처음에는 DFS를 사용하여 모든 경우의 수를 탐색하며 최소 비용을 찾으려고 했다.  
그러나 백트래킹을 사용해도 탐색해야 할 경우의 수가 너무 많아 시간 초과가 발생했다.  
따라서 DP를 이용하여 해결했다.

 

실패코드

def dfs(n, sm):
    global cost
    if n == N:
        if sm < cost:
            cost = sm
        return

    for c in range(3):
        if visited[n-1] != c:
            visited[n] = c
            dfs(n+1, sm+house[n][c])

N = int(input())
house = [list(map(int, input().split())) for _ in range(N)]

visited = [-1]*(N+1)
cost = float('inf')

dfs(0, 0)
print(cost)

 

 

---

 

✅ 성공코드

N = int(input())
house = [list(map(int, input().split())) for _ in range(N)]
dp = [[0]*3 for _ in range(N)]

dp[0] = house[0]
for i in range(1, N):
	# 빨간 집
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + house[i][0]
    
    # 초록 집
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + house[i][1]
    
    # 파란 집
    dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + house[i][2]

print(min(dp[N-1]))  # 마지막 집의 최소 비용 출력