kky9525 2024. 1. 17. 19:19

1149번: RGB거리 (acmicpc.net)

 

1149번: RGB거리

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나

www.acmicpc.net

문제유형

*다이나믹 프로그래밍

문제

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

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

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

입출력 예제

 

(입력 1) 3
26 40 83
49 60 57
13 89 99
(출력 1) 96



(입력 2) 3
1 100 100
100 1 100
100 100 1
(출력 2) 3



풀이

1. 위 문제는 동적프로그래밍 문제이므로, 작은 문제로 쪼개어서 진행을 해야 한다. 따라서, 위 문제를 작은 문제로 쪼개어보면 i번째 집을 빨강, 초록, 파랑 중의 한 색으로 칠했을 때의 최솟값을 구해야 한다. 

2. 먼저, i번째 집에서의 각 색깔의 값을 저장할 배열 color[1001][3]을 선언한다.

3. for문을 통해 1부터 n번째까지의 값을 입력받는다.

4. 최솟값을 구하기 위해서, 다시 for문을 통해 2부터 N번째까지, 위 조건을 만족하는 최솟값을 배열에 갱신한다.

5. 최종적으로 n번째 배열에서의 값끼리 비교를 해서 최솟값을 구할 수 있다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

int N;
int color[1001][3];

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

    cin >> N;
    for (int i=1; i<=N; i++) 
        cin >> color[i][0] >> color[i][1] >> color[i][2];
    
    for (int i=2; i<=N; i++) {
        color[i][0] += min(color[i-1][1], color[i-1][2]);
        color[i][1] += min(color[i-1][0], color[i-1][2]);
        color[i][2] += min(color[i-1][0], color[i-1][1]);
    }
    
    int cost = min(min(color[N][0], color[N][1]), color[N][2]);
    cout << cost;
    
	return 0;
}