[Python/코테] 백준 1149 RGB 거리

백준 1149 RGB 거리

문제 및 조건 설명: https://www.acmicpc.net/problem/1149

 

알고리즘 설계

1. 테이블 정의하기

D[i] = i번째까지의 집을 칠하는 최소 비용 → 규칙을 고려한 점화식이 세워지지 않는다. 🙅🏻‍♀️ → 색상 정보를 포함해야겠다. ❗

D[i][0] = i번째 집까지 칠할 때 비용의 최솟값, 단 i번째 집은 0일 때 빨강/1일 때 초록/2일 때 파랑

 

** dp테이블이란 모든 규칙과 전제를 어기지 않으며, 특정 정보(위치, 색상,.. 등)를 포함하게 된다.

 

2. 점화식 찾기

ex) D[k][0] = ?

D[k][0] = min(D[k-1][1], D[k-1][2]) + R[k]		# 직전 것이 초록-파랑 중 작은 값
D[k][1] = min(D[k-1][0], D[k-1][2]) + G[k]
D[k][2] = min(D[k-1][0], D[k-1][1]) + B[k]

 

3. 초기값 지정

D[1][0] = R[1]
D[1][1] = G[1]
D[1][2] = B[1]

알고리즘 구현

import sys

n = int(input())
r = [0] * 1005
g = [0] * 1005
b = [0] * 1005
d = [[0] * 3 for _ in range(1001)]

for i in range(1, n+1):
    input = list(map(int, sys.stdin.readline().split()))

    r[i] = input[0]
    g[i] = input[1]
    b[i] = input[2]

d[1][0] = r[1]
d[1][1] = g[1]
d[1][2] = b[1]

for i in range(2, n+1):
    d[i][0] = min(d[i-1][1], d[i-1][2]) + r[i]
    d[i][1] = min(d[i-1][0], d[i-1][2]) + g[i]
    d[i][2] = min(d[i-1][0], d[i-1][1]) + b[i]

print(min(d[n][0], d[n][1], d[n][2]))

 

나다어

• 경우의 수가 1~3개로 몇 개 없는 경우, 각각의 조건을 하나의 배열을 활용할 수 있다는 것 기억하기. 뿐만 아니라 r[i], g[i], b[i] 처럼 세 번의 경우를 일일히 실행할 수도 있긴 함.
• dp테이블은 조건을 만족하는 값을 저장하는 것으로, 어떻게 해야 조건 정보를 다 포함할 수 있을 것인가 생각해보기

 

 

 

출처: https://youtu.be/5leTtB3PQu0?si=Ua5xCZ57T-kSXcFv&t=1196