[Python][C++] 1149번 RGB거리

문제

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

 

 

 

 

코드

1. Python

import sys

input = sys.stdin.readline  # 빠른 입력을 위해 sys.stdin.readline 사용

# 집의 수 입력
n = int(input())

# 각 집을 칠하는 비용을 저장할 리스트 p
p = []
for _ in range(n):
    p.append(list(map(int, input().split())))  # 각 집을 칠하는 비용을 입력받아 리스트에 추가

# 1번째 집부터 n번째 집까지 최소 비용을 누적 계산
for i in range(1, n):
    # 현재 집을 빨간색으로 칠하는 최소 비용은 이전 집을 초록색 또는 파란색으로 칠한 비용 중 최소값에 현재 집을 빨간색으로 칠하는 비용을 더한 것
    p[i][0] = min(p[i - 1][1], p[i - 1][2]) + p[i][0]
    
    # 현재 집을 초록색으로 칠하는 최소 비용은 이전 집을 빨간색 또는 파란색으로 칠한 비용 중 최소값에 현재 집을 초록색으로 칠하는 비용을 더한 것
    p[i][1] = min(p[i - 1][0], p[i - 1][2]) + p[i][1]
    
    # 현재 집을 파란색으로 칠하는 최소 비용은 이전 집을 빨간색 또는 초록색으로 칠한 비용 중 최소값에 현재 집을 파란색으로 칠하는 비용을 더한 것
    p[i][2] = min(p[i - 1][0], p[i - 1][1]) + p[i][2]

# n번째 집까지 칠했을 때의 최소 비용을 출력
print(min(p[n - 1][0], p[n - 1][1], p[n - 1][2]))

 

2.C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;  // 집의 수 입력

    vector<vector<int>> cost(n, vector<int>(3));  // 각 집을 칠하는 비용을 저장할 2차원 벡터
    vector<vector<int>> dp(n, vector<int>(3));  // 각 집을 칠할 때의 최소 비용을 저장할 2차원 벡터

    // 각 집의 색상별 비용 입력
    for (int i = 0; i < n; ++i) {
        cin >> cost[i][0] >> cost[i][1] >> cost[i][2];
    }

    // 첫 번째 집을 칠하는 비용은 그대로 사용
    dp[0][0] = cost[0][0];  // 첫 번째 집을 빨간색으로 칠할 때의 비용
    dp[0][1] = cost[0][1];  // 첫 번째 집을 초록색으로 칠할 때의 비용
    dp[0][2] = cost[0][2];  // 첫 번째 집을 파란색으로 칠할 때의 비용

    // 두 번째 집부터 n번째 집까지 최소 비용 계산
    for (int i = 1; i < n; ++i) {
        // 현재 집을 빨간색으로 칠할 경우, 이전 집은 초록색 또는 파란색으로 칠해야 함
        dp[i][0] = cost[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
        // 현재 집을 초록색으로 칠할 경우, 이전 집은 빨간색 또는 파란색으로 칠해야 함
        dp[i][1] = cost[i][1] + min(dp[i - 1][0], dp[i - 1][2]);
        // 현재 집을 파란색으로 칠할 경우, 이전 집은 빨간색 또는 초록색으로 칠해야 함
        dp[i][2] = cost[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
    }

    // 마지막 집까지 칠했을 때의 최소 비용을 계산
    int result = min({ dp[n - 1][0], dp[n - 1][1], dp[n - 1][2] });
    cout << result << endl;  // 결과 출력

    return 0;
}

 

 

 

풀이

 

1. 동적 계획법(DP) 사용:
   • dp[i][j]를 집 i를 색 j로 칠하는 최소 비용으로 정의한다. 여기서 j는 0, 1, 2로 각각 빨강, 초록, 파랑을 나타낸다.
   • 점화식은 다음과 같다:
     • dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0] (현재 집을 빨강으로 칠할 때, 이전 집을 초록 또는 파랑으로 칠한 경우 중 최소 비용을 선택)
     • dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[i][1] (현재 집을 초록으로 칠할 때, 이전 집을 빨강 또는 파랑으로 칠한 경우 중 최소 비용을 선택)
     • dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[i][2] (현재 집을 파랑으로 칠할 때, 이전 집을 빨강 또는 초록으로 칠한 경우 중 최소 비용을 선택)
2. 초기 상태 설정:
   • 첫 번째 집을 칠하는 비용은 각각 주어진 비용 그대로 초기화한다.
     • dp[0][0] = cost[0][0]
     • dp[0][1] = cost[0][1]
     • dp[0][2] = cost[0][2]
3. 최종 결과:
   • 모든 집을 칠한 후, 마지막 집을 빨강, 초록, 파랑 중 어떤 색으로 칠했는지에 상관없이 최소 비용을 구해야 하므로, min(dp[N-1][0], dp[N-1][1], dp[N-1][2])를 결과로 반환한다.