BOJ 1149 · RGB거리

알고리즘 분류 : 다이나믹 프로그래밍  

RGB 거리의 각 집에 색칠하는 비용을 구해야 한다. DP로 구현하여 색칠할 때 드는 최소 비용을 구하면 된다.

• D[N][M] : N번째 집을 M으로 칠할 때 드는 최소 비용 (M은 색깔 0~2)
• D[N][0] : N번째 집을 빨간색(0)으로 칠할 때 드는 최소 비용
• D[N][1] : N번째 집을 초록색(1)으로 칠할 때 드는 최소 비용
• D[N][2] : N번째 집을 파란색(2)으로 칠할 때 드는 최소 비용
• D[1][0] = P[1][0], D[1][1] = P[1][1], D[1][2] = P[1][2]

---

C++ 소스코드

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

int n, d[1001][3], p[1001][3];

void solve() {
    for (int i=0; i<3; i++) d[1][i] = p[1][i];
    for (int i=2; i<=n; i++) {
        d[i][0] = min(d[i-1][1], d[i-1][2]) + p[i][0];
        d[i][1] = min(d[i-1][0], d[i-1][2]) + p[i][1];
        d[i][2] = min(d[i-1][0], d[i-1][1]) + p[i][2];
    }
    printf("%d\n", min(min(d[n][0], d[n][1]), d[n][2]));
}

int main() {
    scanf("%d", &n);
    for (int i=1; i<=n; i++) {
        for (int j=0; j<3; j++) {
            scanf("%d", &p[i][j]);
        }
    }
    solve();
    return 0;
}

---

Python 3 소스코드

def solve():
    for i in range(3):
        d[1][i] = p[1][i]
    for i in range(2, n+1):
        d[i][0] = min(d[i-1][1], d[i-1][2]) + p[i][0]
        d[i][1] = min(d[i-1][0], d[i-1][2]) + p[i][1]
        d[i][2] = min(d[i-1][0], d[i-1][1]) + p[i][2]
    print(min(d[n]))

n = int(input())
d = [[0]*3 for _ in range(n+1)]
p = [[0]*3]+[list(map(int, input().split())) for _ in range(n)]
solve()

---

참고

• 백준 온라인 저지 : BOJ 1149