https://www.acmicpc.net/problem/1149
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
# 2023.01.01
import sys
input = sys.stdin.readline
n = int(input())
RGB = [list(map(int, input().split())) for _ in range(n)]
dp=[[0]*(n) for _ in range(n)]
dp[0][0]=RGB[0][0] #red
dp[0][1]=RGB[0][1] #green
dp[0][2]=RGB[0][2] #blue
for i in range(1, n):
dp[i][0]=min(dp[i-1][1], dp[i-1][2])+RGB[i][0] #red -> 이전: green or blue
dp[i][1]=min(dp[i-1][0], dp[i-1][2])+RGB[i][1] #green -> 이전: red or blue
dp[i][2]=min(dp[i-1][0], dp[i-1][1])+RGB[i][2] #blue -> 이전: red or green
print(min(dp[n-1][0], dp[n-1][1], dp[n-1][2]))dp table을 만들어서 최소의 비용 저장
위에서 아래로 내려오며 min값을 저장
'Problem Solving > BOJ' 카테고리의 다른 글
| [DP] 1932 정수 삼각형 (0) | 2023.01.02 |
|---|---|
| [Divide and Conquer] 1629 곱셈 (0) | 2023.01.01 |
| [DFS] 11725 트리의 부모 찾기 (0) | 2023.01.01 |
| [Greedy] 16953 A->B (1) | 2022.12.31 |
| [Backtracking] 15666 N과 M(12) (0) | 2022.12.30 |