새싹프로그래머의 이야기

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

저번주 부터 다이나믹 프로그래밍 문제를 계속해서 못풀어서 한참 고생했습니다..

기초도 중요하지만 문제를 봤을 때, 사고하는 능력 또한 기를 필요가 있다고 느꼈습니다.

문제: 집의 색이 연속되지 않으면서, 집을 색칠 하는 비용 중 최소인 비용 찾는 문제 입니다.

풀이 방법: 다이나믹 프로그래밍

풀이 코드:

import sys

n = int(sys.stdin.readline())

rgb = []

for _ in range(n):
    rgb.append(list(map(int,sys.stdin.readline().rstrip().split())))

for i in range(1,n):
    rgb[i][0] = min(rgb[i-1][1],rgb[i-1][2]) + rgb[i][0]
    rgb[i][1] = min(rgb[i - 1][0], rgb[i - 1][2]) + rgb[i][1]
    rgb[i][2] = min(rgb[i - 1][0], rgb[i - 1][1]) + rgb[i][2]

print(min(rgb[n-1]))

풀이 설명:

rgb의 비용을 연산하는 for문을 보면 다음과 같습니다.

for i in range(1,n):
    rgb[i][0] = min(rgb[i-1][1],rgb[i-1][2]) + rgb[i][0]
    rgb[i][1] = min(rgb[i - 1][0], rgb[i - 1][2]) + rgb[i][1]
    rgb[i][2] = min(rgb[i - 1][0], rgb[i - 1][1]) + rgb[i][2]

빨간색일 때, 현재 집의 비용에 이전 순서의 초록&파랑색 집의 비용중 최소 값을 더해줍니다.

초록색일 경우, 현재 집의 비용에 이전 순서의 빨강&파랑색 집의 최소 비용을 더해주고

파랑색일 경우, 현재 집의 비용에 이전 순서의 빨강&초록색 집의 최소 비용을 더해줍니다.

이렇게 되면 마지막 집의 비용이 담긴 배열에는 마지막 집의 색상 별로 전체 비용이 담기게 됩니다.

이를 다음과 같이 min 함수를 이용하게 되면 전체 비용중 최소 값이 출력되게 됩니다.

print(min(rgb[n-1]))