[백준 2024/02/28] 1149번 RGB거리

미뿌감 2024. 2. 28. 15:05

728x90

https://www.acmicpc.net/problem/1149

1149번: RGB거리

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나

www.acmicpc.net

1. 접근 방법

dp으로 접근해야겠다고 생각이 들었다.

그 이유로는, 각 단계별 작은 값을 선별해야하기 때문이다.

포인트는 배열에, 선택한 값 + 기존 배열에 저장되어 있는 값을 더한 수 새로 넣어주어야 한다는 점이다.

이렇게 구성해야지, 다음 배열에서 값을 고를 때, 지금까지 골라온 총 값 중에서 최솟값을 선택할 수 있기 때문이다.

2. 코드

def find_min_cost(N, costs):
    dp = [[0 for _ in range(3)] for _ in range(N)]

    for i in range(3):
        dp[0][i] = costs[0][i]

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

    return min(dp[N - 1])


costs = []
n = int(input())
for _ in range(n):
    line = list(map(int, input().split()))
    costs.append(line)

min_cost = find_min_cost(n, costs)
print(min_cost)

728x90