BOJ 17404 - RGB거리 2

출처: https://www.acmicpc.net/problem/17404

---

문제 설명

1~N개의 집 칠하는데, 옆집과는 다른 색으로 칠하는데 필요한 최소 비용. 집의 배치는 원형으로 생각해서 첫집과 마지막집이 이웃이 되도록 한다.

---

입력

집의 수와 각각의 집을 칠하는데 필요한 비용

출력

필요한 최소 비용 

입력 예

3
26 40 83
49 60 57
13 89 99

출력 예

110

제약조건

• 1<= N <= 1000
• 1 <= a_i <= 1000

문제 풀이

RGB거리 문제에서 약간의 변형이 있다. 집들의 시작과 끝이 연결되어 초기조건을 한번 정하는 것으로 결정할 수 없도록 변형됐다. 기본 아이디어는 초기조건과 거기에 따른 제한 조건을 만족하는 최소의 값들을 찾어서, 비교하도록 했다.

첫집을 특정한 색으로 칠하는 경우에 그 색을 제외한 다른 색들은 아주 큰값으로 설정해서 다음번 집 계산에서 선택되지 않도록 해서 마지막 집까지 최소값을 구한다. 마지막집을 칠하는 최소값에서 첫집과 같은 색깔로 칠하는 경우는 배제하고 최소값을 구한다.  

프로그램 내용

const int INF = 987654321;
int tN;

/// 색깔별로 칠하는 최소비용을 계산한다
int minPaint(vector<tuple<int, int, int>>& p_cost, int color);

int main()
{
    cin >> tN;

    /// 각 집을 칠하는 비용 입력
    vector<tuple<int, int, int>> p_cost(tN);
    for(int id=0; id< tN; ++id)
    {
	...
	}

    int cost_r = minPaint(p_cost, 0); // first hosuse red
    int cost_g = minPaint(p_cost, 1); // first hosuse green
    int cost_b = minPaint(p_cost, 2); // first hosuse blue

  	int cost = min({cost_r, cost_g, cost_b}); 

    cout << cost << "\n";

 

관련 문제

 

RGB 거리 (1149)