[Python | 백준] 1149번: RGB거리

 

각 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 인접한 집들이 같은 색이 되지 않도록 하면서 모든 집을 칠하는 최소 비용을 구하는 문제

-> DP 테이블을 2차원 리스트로 정의하여 풀 수 있다.

 

풀이

1. 동적 프로그래밍 테이블 정의:
   • dp[i][j]: i번째 집을 j색으로 칠하는 최소 비용 (j = 0: 빨강, 1: 초록, 2: 파랑)
2. 점화식 설정:
   • dp[i][0] = cost[i][0] + min(dp[i-1][1], dp[i-1][2]) (i번째 집을 빨강으로 칠하는 경우)
   • dp[i][1] = cost[i][1] + min(dp[i-1][0], dp[i-1][2]) (i번째 집을 초록으로 칠하는 경우)
   • dp[i][2] = cost[i][2] + min(dp[i-1][0], dp[i-1][1]) (i번째 집을 파랑으로 칠하는 경우)
3. 초기 조건 설정:
   • 첫 번째 집의 경우, 각각의 색으로 칠하는 비용이 dp 값
   • dp[0][0] = cost[0][0]
   • dp[0][1] = cost[0][1]
   • dp[0][2] = cost[0][2]
4. 결과 값 도출:
   • 마지막 집을 각각의 색으로 칠한 최소 비용 중 가장 작은 값을 찾기
   • result = min(dp[N-1][0], dp[N-1][1], dp[N-1][2])

 

def min_cost(n, costs):

    # DP 테이블 초기화
    dp = [[0] * 3 for _ in range(n)]

    # 첫 번째 집의 비용 초기화
    dp[0][0] = costs[0][0]
    dp[0][1] = costs[0][1]
    dp[0][2] = costs[0][2]

    # DP 테이블 채우기
    for i in range(1, n):
        dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2])
        dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2])
        dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1])

    # 마지막 집을 칠하는 최소 비용 중 최소값 찾기
    return min(dp[n-1][0], dp[n-1][1], dp[n-1][2])


# 입출력
n = int(input())
costs = []
for _ in range(n):
    costs.append(list(map(int, input().split())))

print(min_cost(n, costs))

 

• 입력으로 주어진 집의 수 n과 각 집을 빨강, 초록, 파랑으로 칠하는 비용 costs를 받아서, dp 테이블을 초기화하고 첫 번째 집의 비용을 설정
• 이후, 각 집을 칠할 때의 최소 비용을 점화식을 이용해 계산
• 마지막으로, 마지막 집을 칠한 후의 최소 비용을 구해서 출력