[Python/Baekjoon] B1149. RGB거리

💬 문제

문제 난이도: 실버 1

문제 링크: https://www.acmicpc.net/problem/1149

문제 설명

입력으로 첫 번째 줄에 정수 N(2<=N<=1000), 두번째 줄부터 N개의 줄에는 각 집으로 R, G, B로 칠하는 비용이 주어진다.
이때 비용은 1000보다 작거나 같은 자연수이다.
연속으로 같은 색으로 칠하면 안된다.
집들은 일직선 상에 존재한다.
모든 집을 칠하는 비용의 최솟값으로 출력한다.

❗️접근 방법

DP(dynamic programming) + Greedy

DP 테이블

dp[i][0]
: i번째 집에 R을 칠했을 때 최소비용
dp[i][1]
: i번째 집에 G을 칠했을 때 최소비용
dp[i][2]
: i번째 집에 B을 칠했을 때 최소비용

Greedy

i번째 집을 j로 칠한다면
i-1번째 집을 j가 아닌 다른 색으로 칠한 비용 중 최솟값에
i번째 집을 j로 칠하는 비용을 더하면 된다.

코드

import sys
input = sys.stdin.readline

N = int(input())
dp = [[0, 0, 0] for _ in range(N)]

for i in range(N):
    [R, G, B] = list(map(int, input().split(' ')))
    if (i == 0):
        dp[i] = [R, G, B]
    else:
        dp[i][0] = R + min(dp[i-1][1],dp[i-1][2])
        dp[i][1] = G + min(dp[i-1][0],dp[i-1][2])
        dp[i][2] = B + min(dp[i-1][0],dp[i-1][1])

print(min(dp[N-1]))