[BOJ] 17404. RGB거리 2

Jimeaning·2023년 11월 3일

코딩테스트

목록 보기

126/143

Python3

문제

17404. RGB 거리2

키워드

문제 풀이

문제 요구사항

규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.
N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.
i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다.

변수 및 함수 설명

n: 집의 수 (2 ≤ N ≤ 1,000)
cost: 각 집을 빨강, 초록, 파랑으로 칠하는 비용 (1,000보다 작거나 같은 자연수)
total: 모든 집을 칠하는 비용의 최솟값
dp: 모든 집을 규칙에 맞게 칠하는 비용

풀이

(입력 및 선언)

집의 수와 비용 입력받기

(최저 비용 계산)

dp를 최댓값으로 초기화해서 선언한다.
가장 처음 색(R)은 칠하는 것으로 가정한다.
1부터 n-1까지 돌면서 최저 비용을 dp 안에 넣는다.
- dp[j][0]에는 dp[j-1][1]과 dp[j-1][2] 중 작은 값과 현재 비용 cost[j][0]을 더한다.
- dp[j][1]에는 dp[j-1][0]과 dp[j-1][2] 중 작은 값과 현재 비용 cost[j][1]을 더한다.
- dp[j][2]에는 dp[j-1][0]과 dp[j-1][1] 중 작은 값과 현재 비용 cost[j][2]을 더한다.
이전 집과 현재 집이 같은 건 카운트하지 않기 위해서 i와 j가 서로 다를 때만 total에 더한다.

최종 코드

n = int(input())

total = float("INF")
cost = []

for _ in range(n):
    cost.append(list(map(int, input().split())))

for i in range(3):
    dp = [[float("INF"), float("INF"), float("INF")] for _ in range(n)]

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

    for j in range(3):
        if i != j:
            total = min(total, dp[-1][j])

print(total)