백준 1149번 [RGB거리](C++) -yes6686- 티스토리

백준 문제 풀이: 1149 [RGB거리]

---

문제 링크: https://www.acmicpc.net/problem/1149

문제 설명:

RGB거리에는 집이 n개 있으며, 각 집은 빨강(R), 초록(G), 파랑(B) 중 하나의 색으로 칠해야 합니다. 또한, 인접한 두 집은 같은 색을 가질 수 없습니다. 각 집을 칠하는 비용이 주어졌을 때, 모든 집을 칠하는 데 드는 최소 비용을 구하는 프로그램을 작성하세요.

입력:

• 첫째 줄에 집의 수 n이 주어집니다. (2 ≤ n ≤ 1,000)
• 둘째 줄부터 n개의 줄에는 빨강, 초록, 파랑으로 칠하는 비용이 주어집니다. (1 ≤ 비용 ≤ 1,000)

출력:

• 모든 집을 칠하는 데 드는 최소 비용을 출력합니다.

예시:

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

출력:
96

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

int arr[1001][3]; // 각 집의 칠하는 비용
int dp[1001][3];  // 최소 비용

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> arr[i][j];
        }
    }

    // 첫 번째 집의 비용 초기화
    for (int j = 0; j < 3; j++) {
        dp[0][j] = arr[0][j];
    }

    // 동적 프로그래밍으로 최소 비용 계산
    for (int i = 1; i < n; i++) {
        dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + arr[i][0]; // 빨강으로 칠할 경우
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + arr[i][1]; // 초록으로 칠할 경우
        dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + arr[i][2]; // 파랑으로 칠할 경우
    }

    // 마지막 집의 최소 비용 중 최솟값 찾기
    int result = min({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]});

    cout << result << '\n';
    return 0;
}

---

코드 설명

이 코드는 동적 프로그래밍(DP)을 사용하여 각 집을 칠하는 최소 비용을 계산합니다. 주요 로직과 알고리즘은 다음과 같습니다:

• 핵심 알고리즘:
  • 각 집을 특정 색으로 칠할 때의 최소 비용은, 이전 집을 다른 색으로 칠한 최소 비용에 현재 집의 비용을 더한 값입니다.
  • 점화식:
    • dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[i][0] (빨강)
    • dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + arr[i][1] (초록)
    • dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + arr[i][2] (파랑)
• 구현 세부사항:
  • dp[i][j]는 i번째 집을 j색으로 칠할 때의 최소 비용을 나타냅니다.
  • 각 집마다 3가지 색에 대한 최소 비용을 갱신하며 계산합니다.
• 시간 복잡도 분석:
  • DP 계산: O(n)
  • 최종 결과 탐색: O(1)
  • 전체 시간 복잡도: O(n)

---

결과

코드는 입력된 집의 칠하는 비용 배열을 사용하여 최소 비용을 효율적으로 계산합니다. 동적 프로그래밍을 활용하여 O(n)의 시간 복잡도로 문제를 해결하며, 큰 입력에서도 적절히 작동합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!