[백준 1149] RGB 거리 문제

[git] 백준 1149, RGB거리

문제 출처 - https://www.acmicpc.net/problem/1149

---

 

문제

---

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 처음 집과 마지막 집은 이웃이 아니다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다.

 

출력

---

첫째 줄에 모든 집을 칠할 때 드는 비용의 최솟값을 출력한다.

 

 

예제 입력

3
26 40 83
49 60 57
13 89 99

예제 출력

96

• 문제 이해하기

집에 빨강, 초록, 파랑 중에 하나로 색을 칠해야 한다. 단, 이웃하는 집은 같은 색깔로 칠할 수 없다. 처음에 주어진 N의 수만큼, 각각 빨강, 초록, 파랑으로 칠할 때 비용을 입력해준다. 그리고 모든 집을 칠하는데 드는 최소 비용을 구하는 문제다.

즉, 처음에 가장 비용이 적은 색깔로 시작하더라도, 이후에 입력한 비용의 값에 따라 최소 비용이 달라질 수 있는 문제다. 따라서 모든 경우의 수를 다 생각하면서 진행해야 원하는 최소 비용을 구할 수 있을 것이다.

문제에 주어진 예제 입력 결과를 다시 보자.

1 2 3 4

3 26 40 83 49 60 57 13 89 99

cs

총 3개의 집의 수가 입력 되었고, 각각 빨강, 초록, 파랑 순서로 비용이 입력 되었다.

현재 주어진 예제의 최소비용은 26 + 57 + 13 = 96이 된다.

이처럼 두번째 집에서 49가 최소 비용이지만, 같은 빨간색이기 때문에 적용할 수 없다는 것을 생각해야 하는 문제다.

 

• 계획 및 문제 해결

우리에게 주어진 색깔은 총 3가지다. 따라서 빨강, 초록, 파랑으로 시작하는 최소 비용을 각각 구해 배열에다가 저장하는 방법을 생각했다. 이 3가지 배열 중에 가장 작은 값이 최소 비용이 될 것이다. 배열을 만들어보자.

int RGB[3];

메인 함수에서 알아보기 쉽게 쓰기 위해 배열을 enum 값으로 나타내자. R, G, B로 나타내면 편할 것이다.

 eum { R, G, B }; // 0, 1, 2를 R, G, B로 나타내자

이제 배열 설정은 끝났고, 이를 메인 함수에서 사용해 원하는 값을 구해보자.

우선 집의 수 N을 입력하고, 색의 비용을 입력할 변수를 만들자.

int N;
cin >> N;
​
int r, g, b;

이제 N만큼 반복문을 돌려서, 빨강 초록 파랑 값을 입력해야 한다.

우리는 미리 설정한 RGB배열에 반복문이 돌 때마다 최소값을 입력시키면 된다.

 

기존의 저장된 값을 활용해서 값을 구하기 위해, RGB 배열의 값을 각각 int형 변수를 만들어 저장시켜 활용한다.

int sumR = RGB[R], sumG = RGB[G], sumB = RGB[B];

이제 이 값을 통해 최소 비용을 구할 것이다. 각 배열마다 값은 반복문에서 이렇게 증가할 것이다.

cin >> r >> g >> b;
​
RGB[R] = r + min(sumG, sumB);
RGB[G] = g + min(sumR, sumB);
RGB[B] = b + min(sumR, sumG);

이와 같은 코드를 통해, 자신과 중복되는 색깔은 더해지지 않을 수 있음을 알 수 있다.

자신을 제외한 나머지 두 색에서 min을 통해 최소를 찾아내 해당 색의 입력 값을 더해가면 된다.

반복문을 통해 완성된 코드는 다음과 같다.

for (int i = 0; i < N; i++) {
        int sumR = RGB[R], sumG = RGB[G], sumB = RGB[B];
        cin >> r >> g >> b;
​
        RGB[R] = r + min(sumG, sumB);
        RGB[G] = g + min(sumR, sumB);
        RGB[B] = b + min(sumR, sumG);
}

반복문이 모두 끝나면, 빨강 초록 파랑으로 시작된 최소비용 값이 각각 배열에 저장되었을 것이다. 이제 이 3가지 배열의 값을 비교해 가장 작은 값을 출력하자.

cout << min(RGB[R], min(RGB[G], RGB[B]));

위처럼 RGB[G]와 RGB[B]중에 작은 값을, RGB[R]과 다시한번 비교해서 작은 값을 구해오면 될 것이다.

 

• 전체 소스 코드

#include <iostream>
#include <algorithm>
​
using namespace std;
​
int RGB[3];
enum { R, G, B };
​
​
int main(void) {
​
    int N;
    cin >> N;
​
    int r, g, b;
​
    for (int i = 0; i < N; i++) {
        int sumR = RGB[R], sumG = RGB[G], sumB = RGB[B];
        cin >> r >> g >> b;
​
        RGB[R] = r + min(sumG, sumB);
        RGB[G] = g + min(sumR, sumB);
        RGB[B] = b + min(sumR, sumG);
    }
    
    cout << min(RGB[R], min(RGB[G], RGB[B]));
    return 0;
}