문제링크: 백준 1149번: RGB거리

해당 문제는 DP(dynamic programming. 다이나믹 프로그래밍) 문제입니다.
dp란 큰 문제를 작은 문제로 나누어 해결하는 기법입니다.

다이나믹 프로그램은 다음의 가정 하에 사용할 수 있습니다.
1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 다른 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

---

풀이 코드

#include <iostream>
using namespace std;

int painting[1001][3];

void insertInput(int i) {
    cin >> painting[i][0] >> painting[i][1] >> painting[i][2];
}

void storePaintingCounts(int i) {
    painting[i][0] += min(painting[i - 1][1], painting[i - 1][2]);
    painting[i][1] += min(painting[i - 1][0], painting[i - 1][2]);
    painting[i][2] += min(painting[i - 1][0], painting[i - 1][1]);
}

void solve(int n) {
    for (int i = 0; i < n; i++) {
        insertInput(i);
		if (i > 0)
			storePaintingCounts(i);
    }
}

void printResult(int n) {
    cout << min(min(painting[n][0], painting[n][1]), painting[n][2]) << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    solve(n);
    printResult(n - 1);
    return 0;
}

---

코드 설명

이러한 input 이 들어온다고 가정해봅니다.

painting[i][0], painting[i][1], painting[i][2] 에는 각각 i 번째 집을 각각 빨간색, 초록색, 파란색으로 칠할 때의 누적 최소비용을 저장합니다.

i 번째 집을 특정 색으로 칠할 때, i - 1 번째 집을 해당 색이 아닌 다른 색으로 칠했을 때의 누적 최소비용 중 더 작은 값을 골라, 현재 색의 비용을 더합니다.

마지막 집까지 칠한 뒤, painting[n - 1][0], painting[n - 1][1], painting[n - 1][2] 의 값 중 최솟값이 전체 비용의 최솟값이 됩니다.

위의 예시의 경우, 전체 비용의 최솟값은 3이 되겠습니다.