[백준/Python] 1149 RGB거리

[백준/Python] 1149 RGB거리

정답 코드 및 설명

전체 코드

def find_min_cost(cost, N):
    dp = [[0 for _ in range(3)] for _ in range(N)]

    for color in range(3):
        dp[0][color] = cost[0][color]

    for i in range(1, N):
        dp[i][0] = cost[i][0] + min(dp[i-1][1], dp[i-1][2])
        dp[i][1] = cost[i][1] + min(dp[i-1][0], dp[i-1][2])
        dp[i][2] = cost[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())
# 각 집을 빨강, 초록, 파랑으로 칠하는 비용 입력 받기
cost = []
for _ in range(N):
    cost.append(list(map(int, input().split())))

# 최소 비용 계산 및 출력
min_cost = find_min_cost(cost, N)
print(min_cost)

코드 설명

1. 사용자로부터 집의 수 N을 입력받는다.
2. 사용자로부터 각 집을 빨강, 초록, 파랑으로 칠하는 비용을 입력받는다. 각 비용은 공백으로 구분되며, N번 반복하여 입력받는다.
3. 입력받은 비용을 바탕으로 모든 집을 칠하는 최소 비용을 계산한다.
4. 계산된 최소 비용을 출력한다.

주요 함수 설명

def find_min_cost(cost, N):
    dp = [[0 for _ in range(3)] for _ in range(N)]

    for color in range(3):
        dp[0][color] = cost[0][color]

    for i in range(1, N):
        dp[i][0] = cost[i][0] + min(dp[i-1][1], dp[i-1][2])
        dp[i][1] = cost[i][1] + min(dp[i-1][0], dp[i-1][2])
        dp[i][2] = cost[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])

위 문제를 해결하기 위해 작성한 코드로 문제에 주어진 집들을 RGB 색상으로 칠할 때, 각 색상별로 비용이 주어지고 인접한 집들이 같은 색으로 칠해지지 않도록 하면서 전체 비용을 최소화하는 문제에 적용하는 함수이다.

cost 각 집을 R G B 로 칠해하는 데 드는 비용을 저장한 2차원 리스트이다.
cost[i][0], cost[i][1], cost[i][2]는 각각 i번째 집을 R, G, B로 칠하는 비용이다.
N은 집의 총 수를 나타내는 정수이다.

함수 동작 과정

1. DP 테이블 초기화: dp 테이블은 각 집을 R, G, B로 칠할 때까지의 최소 비용을 저장한다. dp[i][color]는 0번째부터 i번째 집까지 고려했을 때, 마지막 집(i번째 집)을 color 색으로 칠했을 때의 최소 비용이다.

2. 첫 번째 집 칠하기: 첫 번째 집을 R, G, B로 칠하는 비용을 dp[0][color]에 저장한다. 이는 초기 조건을 설정하는 단계이다.

3. 점화식을 통한 최소 비용 계산:

각 집 i에 대해, dp[i][color]를 계산한다. 이는 "i번째 집을 특정 색으로 칠했을 때의 비용 + i-1번째 집을 다른 두 색 중 하나로 칠했을 때의 최소 비용"으로 정의된다. 예를 들어, dp[i][0] (i번째 집을 R로 칠하는 경우)의 비용은 cost[i][0] + min(dp[i-1][1], dp[i-1][2])로 계산된다. 여기서 cost[i][0]은 i번째 집을 R로 칠하는 비용이고, min(dp[i-1][1], dp[i-1][2])는 이전 집(i-1번째 집)을 G나 B로 칠했을 때의 최소 비용이다.

4. 최소 비용의 결정:

모든 집을 칠했을 때의 최소 비용은 min(dp[N-1][0], dp[N-1][1], dp[N-1][2])로 결정된다. 이는 마지막 집(N-1번째 집, 인덱스는 0부터 시작하므로)을 R, G, B 중 어떤 색으로 칠했을 때의 최소 비용 중 가장 작은 값을 의미한다.