RGB거리

import sys


raw = sys.stdin.readlines()
n = int(raw[0])
c = [[int(x) for x in line.split()] for line in raw[1:]]
dp = [[0,0,0] for _ in range(n)]
dp[0] = c[0]
for i in range(1, n):
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + c[i][0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + c[i][1]
    dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + c[i][2]
print(min(dp[n-1]))

이 코드는 집을 칠하는 데 필요한 최소 비용을 계산하는 동적 계획법(Dynamic Programming, DP) 알고리즘의 구현입니다. 문제의 설정은 다음과 같습니다: 여러분은 n개의 집을 칠해야 하며, 각 집을 빨강, 초록, 또는 파랑으로 칠할 수 있습니다. 각 색을 칠하는 데 드는 비용이 주어지고, 인접한 집들은 같은 색으로 칠할 수 없습니다. 목표는 모든 집을 규칙에 맞게 칠하는 데 필요한 총 비용의 최솟값을 찾는 것입니다.

코드의 핵심 부분을 단계별로 설명하겠습니다:

1. 모듈 임포트 및 입력 받기:
   import sys raw = sys.stdin.readlines()
   • sys.stdin.readlines()를 사용하여 입력을 받습니다. 이 방법은 입력을 한 번에 모두 읽어서 각 줄을 리스트의 요소로 저장합니다. 표준 입력에서 여러 줄을 읽을 때 유용합니다.
2. 입력 데이터 처리:
   n = int(raw[0]) c = [[int(x) for x in line.split()] for line in raw[1:]]
   • 첫 번째 줄(raw[0])에서 집의 개수 n을 읽습니다.
   • 두 번째 줄부터는 각 집을 빨강, 초록, 파랑으로 칠하는 데 드는 비용을 읽어 c 리스트에 저장합니다. c는 2차원 리스트로, c[i][j]는 i번째 집을 j색으로 칠하는 데 드는 비용을 나타냅니다.
3. 동적 계획법(DP) 배열 초기화:dp[0] = c[0]`
   • dp 배열은 각 집을 칠하는 데 드는 최소 비용을 저장합니다. dp[i][j]는 0번째부터 i번째 집까지 칠하는 데 드는 최소 비용을 나타내며, i번째 집은 j색으로 칠해집니다.
   • 첫 번째 집(dp[0])은 직접 비용을 할당합니다. 첫 번째 집을 칠하는 데 드는 비용은 입력에서 주어진 그대로입니다.
4. `dp = [[0,0,0] for _ in range(n)]
5. DP를 사용한 최소 비용 계산:
   `for i in range(1, n):
   • 각 집에 대해, 이전 집이 다른 두 색으로 칠해진 경우 중 최소 비용을 현재 집을 칠하는 비용에 더합니다. 이렇게 하여, 어떤 집도 인접한 집과 같은 색으로 칠해지지 않게 하면서, 최소 비용을 계산합니다.
6. dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + c[i][0] dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + c[i][1] dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + c[i][2]`
7. 최종 결과 출력
   print(min(dp[n-1]))
   • 마지막 집까지 칠하는 데 드는 최소 비용 중에서 가장 작은 값을 출력합니다. 이 값은 모든 집을 규칙에 맞게 칠하는 데 필요한 총 비용의 최솟값입니다.

이 알고리즘은 동적 계획법의 기본 원리인 "부분 문제의 최적 해를 구하여 전체 문제의 최적 해를 찾는" 방식을 따릅니다. 각 단계에서 최적의 결정을 취함으로써, 최종적으로 전체 문제에 대한 최적의 해결책을 도출합니다.