백준 실버1 1149. RGB거리 (python)

RGB거리

 

풀이

양옆의 집의 색이 모두 달라야 한다는 조건이다.
빨강, 초록, 파랑 중 하나로 칠해야하는데, 이 3가지를 이용해 모든 집을 가장 최소비용이 나오도록 칠해야 하는 문제다.
아래처럼 풀었다.

1. 집의 갯수 N과 집마다 칠 할 때 비용을 입력받음.
2. 각 집을 칠하는 비용 최솟값을 저장할 배열을 생성.
3. 맨 처음 집을 칠할 때 비용을 미리 작성
4. 각 집을 돌면서 지금까지의 비용을 산정, 이때, 빨강, 초록, 파랑의 색을 고르되 이전 집과의 색이 다르도록 비용을 산정
5. 모든 집이 산정이 다 되었을 경우, 마지막으로 가장 적은 비용 산정이 된 것을 고르고 출력

import sys

def solve(N, costs):
    # 각 집을 칠하는 비용의 최솟값을 저장할 dp 배열 생성
    dp = [[0] * 3 for _ in range(N)]
    
    # 초기 상태 설정: 첫 번째 집을 각각의 색으로 칠하는 비용
    dp[0] = costs[0]

    # 두 번째 집부터 마지막 집까지 반복하면서 최솟값 계산
    for i in range(1, N):
        # 현재 집을 빨강(R)으로 칠하는 경우
        dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i][0]

        # 현재 집을 초록(G)으로 칠하는 경우
        dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i][1]

        # 현재 집을 파랑(B)으로 칠하는 경우
        dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i][2]

    # 마지막 집을 칠한 후에는 세 가지 색 중에서 가장 작은 값을 선택
    return min(dp[N-1])

# 입력 받기
N = int(sys.stdin.readline())       # 집의 개수
costs = []                          # 각 집을 칠하는 비용을 저장할 리스트
for _ in range(N):
    costs.append(list(map(int, sys.stdin.readline().split())))

# 문제 해결 및 결과 출력
answer = solve(N, costs)
print(answer)