[1149] RGB거리

😲 문제

출처
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

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

입력
3
26 40 83
49 60 57
13 89 99

출력
96

❗️ 문제 재정의

1. 1번부터 n번까지의 집이 순서대로 존재한다.
2. 빨강 초록 파랑 중 하나의 색으로 칠해야한다.
3. 색은 연속적으로 같으면 안된다.
4. 입력은 집이 n개가 있고 각 집에 대한 빨 초 파로 칠할 때의 비용이 각각 주어진다.

DP를 사용한 누적 비용 문제이다.
2차원 배열에서 각각의 칸에 도착하는 최적의 비용을 찾아야 한다.
즉, 인접 노드와 색이 겹치지 않으면서 가장 비용이 낮은 값을 찾아야 한다.
각 최적의 비용은 그 전의 최적의 비용에 자신의 비용의 합이라는 사실이다.

d[i][j] = min(d[i-1][z]) + d[i][j] 인데
조건은 인덱스가 겹치지 않는 것들 중 가장 작은 값인가이다.

✔ 계획 수립

1. 입력 받기 집의 개수 n개
2. 입력 받기 각각의 집에 대한 색깔비용 2차원 배열 rgbs
3. 2번째 집부터 방문하며 자신의 인덱스가 아닌가를 체크
4. rgbs[i][j] = min(rgbs[i-1][z]) + rgbs[i][j] j!=z이다.
5. 마지막까지 누적된 리스트 중 가장 작은 값 출력

👨🏻‍💻 문제 풀이

n = int(input())
# 마지막 요소의 최솟값이 어떤 요소들의 조합으로 이루어져있는가?
# 그 전의 요소의 최솟값의 조합이다.
rgbs = [list(map(int, input().split())) for _ in range(n)]
# 각가의 인덱스에 자기 인덱스가 아닌 것들 중 가장 작은 값을 선택
for i in range(1,n):
    for j in range(3):
        if j==0:
            rgbs[i][j] += min(rgbs[i-1][j+1], rgbs[i-1][j+2])
        elif j==1:
            rgbs[i][j] += min(rgbs[i-1][j-1], rgbs[i-1][j+1])
        else:
            rgbs[i][j] += min(rgbs[i-1][j-1], rgbs[i-1][j-2])
print(min(rgbs[-1]))

😅 회고

매우 쉽게 푼 문제이다. 솔직히 실버1이 아니라 실버3은 되는 듯 싶다.

외부 루프: for i in range(1, n)는 1부터 n-1까지 반복이다. 따라서, 외부 루프의 반복 횟수는 n-1이다.

내부 루프: for j in range(3)는 0부터 2까지 반복이다. 이는 상수 시간 반복으로, 3번 반복이다.

각 집에 대해, 세 가지 색상 옵션 각각에 대해 최소 비용을 계산! 이 계산은 상수 시간 작업이다. 따라서, 내부 루프의 각 반복은 O(1)의 시간 복잡도를 가진다.

전체 시간 복잡도는 외부 루프와 내부 루프의 반복 횟수를 곱한 것이다. 외부 루프는 n-1번 반복되고, 내부 루프는 상수 시간인 3번 반복된다. 따라서, 전체 시간 복잡도는 O(n-1) * O(3)이다. 여기서 O(3)은 상수이므로, 전체 시간 복잡도는 O(n)으로 간주할 수 있다.