[c++] BOJ 1149 :: RGB거리

난이도 : 실버 1

걸린 시간 : 30분

 

문제

1149. RGB 거리

 

풀이

• 최종적으로 구하고자 하는 것 : 양쪽과 색이 같지 않은 집으로 모든 집을 칠하는 비용의 최소값
• 부분 문제 : 현재 집에서 비용의 최소값
• 재귀 (집의 index, 집의 색깔) => 비용의 최소값
• 현재 집을 칠하는 데에 드는 비용의 최소 = 3가지 색 중의 최소 = 지금의 값 + 오른쪽 집의 최소값
• 조건
  • 오른쪽 집은 색이 겹치지 않아야함
    • for문에서 색이 겹치면 continue
  • 마지막 집은 오른쪽 집이 없으므로 가격이 그 자체로 최소값
    • memo에 미리 저장해두는 것으로 해결
• DP 사용
  • 겹치는 부분 : 현재 집의 색에서 나타나는 비용의 최소값
    • (index, color) => 최소
    • 저장은 R, G, B color 각각을 모두 해야하므로 주어진 배열과 같이 열이 3인 2차원 배열로 표현

 

코드

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int N;
int house[1000][3];
int memo[1000][3];

int lowestValue(int idx, int color) {
    int value = 1e9;
    for (int i = 0; i < 3; i++) {
        if (color == i) // 이전 색과 똑같지 않게
            continue;
        int tmp;
        if (memo[idx+1][i] != -1) {
            // 이미 했으면
            tmp = house[idx][color] + memo[idx+1][i];
        }
        else {
            tmp = house[idx][color] + lowestValue(idx + 1, i);
        }
        value = tmp < value ? tmp : value; // RGB 중 최소값 찾기
    }
    memo[idx][color] = value;
    return value;
}

int main() {
    // 입력 받기
    cin >> N;

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

    // 초기화
    memset(memo, -1, sizeof(memo));
    for (int i = 0; i < 3; i++) {
        // 마지막 집은 다음 집이 없으므로 memo 미리 등록
        memo[N - 1][i] = house[N - 1][i];
    }

    int answer = 1e9;
    for (int i = 0; i < 3; i++) {
        // 첫번째 집 RGB에 대해 모두 조사
        int tmp = lowestValue(0, i);
        answer = answer < tmp ? answer : tmp;
    }
    cout << answer;
}

 

결과

DP 문제를 좀 더 풀어봐야할 것 같아서 풀어봤는데, 이전에 문제를 풀었을 때와 비교해서 훨씬 나아졌다.