[BOJ] #1149 RGB 거리

RGB거리

백준 #1149

---

📌 문제

예제 입력

3
26 40 83
49 60 57
13 89 99

예제 출력

96

---

📌 풀이

Logic

• 집의 수 N 입력 받기
• 각 집의 RGB 비용 입력 받기
• DP 테이블 생성
  • dp[i][j] -> i번재 집을 j색으로 색칠
  • 첫 번째 집은 입력값 그대로
  • 마지막 집까지 계산 후 최소값 출력

# 변수명
N : 집의 수
cost : 각 집의 RGB 색칠 비용 리스트

Python

import sys

N = int(sys.stdin.readline())
cost = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dp = [[0] * 3 for _ in range(N)]
dp[0] = cost[0]

for i in range(1, N):
    dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0]
    dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1]
    dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2]

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

---

✏️ 새로운 내용

-

---

📚 회고

💡 DP

• 예전에 잠시 다루어봤던 유형이므로 빠르게 훑어보고 넘어가려고 한다.
• 낮은 단계의 문제만 풀었기도 하고, 다음 학기 '알고리즘' 과목에서 해당 주제의 챕터가 있는 것을 확인했기에 미리 다뤄보려고 한다.