알고리즘💻/DP
BOJ 1149번: RGB거리
호프
2021. 5. 5. 03:31
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
문제풀이:
dp를 어떻게 짜야 할 지 생각해내는 것이 어려웠다.
최솟값을 더하는 방법으로 하자니 동일한 비용이 나오는 경우를 고려하는 것이 어려웠고..
그래서 각각의 경우를 모두 구하는 것이구나 하는 걸 깨달았다..(사실 힌트를 좀 받았다..)
그걸 깨닫고 나니 푸는 것은 간단했다.
import sys
N = int(sys.stdin.readline())
cost = []
for _ in range(N):
cost.append(list(map(int, sys.stdin.readline().split())))
dp = [[0,0,0] for _ in range(N)]
dp[0] = cost[0]
for i in range(1,N):
dp[i][0] = min(dp[i-1][1]+cost[i][0], dp[i-1][2]+cost[i][0])
dp[i][1] = min(dp[i-1][0]+cost[i][1], dp[i-1][2]+cost[i][1])
dp[i][2] = min(dp[i-1][0]+cost[i][2], dp[i-1][1]+cost[i][2])
print(min(dp[N-1][0], dp[N-1][1], dp[N-1][2]))