BOJ_1149 C++

HDuckkk·2023년 1월 11일
0

Beakjoon Online Judge

목록 보기
1/13
post-thumbnail

BOJ 1149 RGB거리

문제
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

  • 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
  • N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
  • i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

풀이 과정

우선 위의 3가지 조건에 집중했다. 간단히 요약하자면 인접하는 두 집의 색이 서로 달라야 한다는 것이다. 인접하는 두 집의 색이 서로 다르면서 페인트 비용이 최소가 되어야 한다는 것이 이 문제의 핵심이다.

우선 모든 경우의 수를 따지는 접근방법을 생각했다. 즉, 칠할 수 있는 색의 모든 경우의 수를 따진 후 그 중 페인트칠 값이 최소가 되는 경우 하나를 차출하는 접근이었다. 그러나 이 경우는 집의 수가 많아짐에 따라 경우의 수가 급격히 많아져 제한된 시간 내에 해답을 내놓기가 어려웠다.

따라서 문제를 나누어서 해결해야 했다. 순서대로 각 집을 칠해 나가면서 각각의 색을 칠할 경우의 최소 가격을 배열에 저장해 나가는 방법을 생각했다.

//BOJ 1149
#include <iostream>
using namespace std;

// 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
// N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
// i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
// --> 집을 세가지 색으로 칠할 때 각각의 최소값을 저장해나간다.

int house[1001][3]; // 0:RED, 1:GREEN, 2:BLUE 

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

    // 집의 수 N
    int N;
    cin >> N;

    for(int i=1; i<=N; i++){
        int R, G, B;
        cin >> R >> G >> B; //0:R, 1:G, 2:B

        house[i][0] = min(house[i-1][1],house[i-1][2]) + R;
        house[i][1] = min(house[i-1][2],house[i-1][0]) + G;
        house[i][2] = min(house[i-1][0],house[i-1][1]) + B;
    }

    cout << min(house[N][0], min(house[N][1], house[N][2]) );

    return 0;
}

여기서 핵심이 되는 내용은 반복문 안의 내용인데 다음과 같다.

for(int i=1; i<=N; i++){
        int R, G, B;
        cin >> R >> G >> B; //0:R, 1:G, 2:B

        house[i][0] = min(house[i-1][1],house[i-1][2]) + R;
        house[i][1] = min(house[i-1][2],house[i-1][0]) + G;
        house[i][2] = min(house[i-1][0],house[i-1][1]) + B;
    }

즉, 모든 경우의 수를 따지는 것이 아니라 처음부터 색을 하나 하나 칠해가며 경우의 수를 따지는 것이다. 그럼 다음과 같은 규칙을 확인할 수 있다.

  • 빨간색으로 칠 할 경우, 이전에 칠했던 색이 초록색 혹은 파란색이며 그 중 적은 가격으로 칠할 수 있는 색을 이용.
  • 파란색으로 칠 할 경우, 이전에 칠했던 색이 빨간색 혹은 초록색이며 그 중 적은 가격으로 칠할 수 있는 색을 이용.
  • 초록색으로 칠 할 경우, 이전에 칠했던 색이 빨간색 혹은 파란색이며 그 중 적은 가격으로 칠할 수 있는 색을 이용.

이 규칙을 적용 할 경우 집이 최대 1000개가 존재 한다고 하더라도 약 3000번의 연산을 거치면 최소값을 구하는 것이 가능하다.

Summary

  • 모든 경우의 수를 확인하는 경우, 많은 연산으로 인해 연산시간이 너무 오래 걸린다.
  • 인접하는 두 집의 색이 서로 다르다는 조건을 하나씩 칠해가면 값을 저장하는 사고로 접근하면 상당히 간단하게 해결할 수 있다.
  • 다양한 DP문제를 풀어보며 이와 같은 문제의 감을 익히는 것이 중요하다고 생각된다.

0개의 댓글