백준 17404 RGB 거리 2

문제 링크 : https://www.acmicpc.net/problem/17404

17404번: RGB거리 2

풀이

다이내믹 프로그래밍 문제입니다!

RGB거리에 사는 사람들은 빨강, 초록, 파랑 3가지 색 중 하나로 집을 칠해야하는데, 

인접한 집의 색이 같으면 안된다.

 

따라서 i번째 집의 색은 i-1번째 집의 색에 따라 경우의 수가 나뉘는데,

예를 들어 i-1번째 집이 빨간색이라면, i번째집은 i-1번째 집이 초록, 파랑일 때 1부터 i-1번째 집까지 색칠하는 경우의 수를 모두 더해주면 된다.

 

따라서 dp로 표현하자면 D[i][j] = i번 째 집이 j색일 경우의 비용의 최솟값 이라고 표현 가능하다.

 

단, 이 문제는 첫 집과 마지막 집도 이웃인 원형 마을의 구조를 갖기 때문에

첫 집을 고정 해둔 채 마지막 집의 색을 구해줘야 한다.

 

따라서, d[i][j] 배열을 색깔에 따라 3가지 만들어주고, i가 n번 째 집일 경우 반드시 첫 번째 집의 색과 다른 색으로 칠하는 경우의 수를 구해주면 된다.

 

소스 코드

#include <iostream>
#include <algorithm>
using namespace std;
 
int red[3][1001];
int green[3][1001];
int blue[3][1001];
int r[1001]; int g[1001]; int b[1001];
int main()
{
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &r[i], &g[i], &b[i]);
    }
    // 0: red, 1 : green, 2 : blue
    red[0][1] = r[1];
    red[1][2] = r[1] + g[2]; red[2][2] = r[1] + b[2]; red[0][2] = 9999;
    for (int i = 3; i < n; i++) {
        red[0][i] = min(red[1][i - 1], red[2][i - 1]) + r[i];
        red[1][i] = min(red[0][i - 1], red[2][i - 1]) + g[i];
        red[2][i] = min(red[0][i - 1], red[1][i - 1]) + b[i];
    }
    red[1][n] = min(red[0][n - 1], red[2][n - 1]) + g[n];
    red[2][n] = min(red[0][n - 1], red[1][n - 1]) + b[n];
    int min_red = min(red[1][n], red[2][n]);
 
    //green
    green[1][1] = g[1];
    green[0][2] = g[1] + r[2]; green[2][2] = g[1] + b[2]; green[1][2] = 9999;
    for (int i = 3; i < n; i++) {
        green[0][i] = min(green[1][i - 1], green[2][i - 1]) + r[i];
        green[1][i] = min(green[0][i - 1], green[2][i - 1]) + g[i];
        green[2][i] = min(green[0][i - 1], green[1][i - 1]) + b[i];
    }
    green[0][n] = min(green[1][n - 1], green[2][n - 1]) + r[n];
    green[2][n] = min(green[0][n - 1], green[1][n - 1]) + b[n];
    int min_green = min(green[0][n], green[2][n]);
 
    //blue
    blue[2][1] = b[1];
    blue[0][2] = b[1] + r[2]; blue[1][2] = b[1] + g[2]; blue[2][2] = 9999;
    for (int i = 3; i < n; i++) {
        blue[0][i] = min(blue[1][i - 1], blue[2][i - 1]) + r[i];
        blue[1][i] = min(blue[0][i - 1], blue[2][i - 1]) + g[i];
        blue[2][i] = min(blue[0][i - 1], blue[1][i - 1]) + b[i];
    }
    blue[0][n] = min(blue[1][n - 1], blue[2][n - 1]) + r[n];
    blue[1][n] = min(blue[0][n - 1], blue[2][n - 1]) + g[n];
    int min_blue = min(blue[0][n], blue[1][n]);
    int ans = min(min_red, min(min_green, min_blue));
    printf("%d\n", ans);
 
    return 0;
}

실력이 모자라서 배열도 많고 코드도 길어진거같다 ㅠㅠ

처음 집이 fix가 되기 때문에 각각의 D 배열은 최소 2번째 집까지는 지정을 해주어야

무난하게 점화식으로 풀 수 있었다. (아마 다른 곳에 더 좋은 코드가 있을겁니당 ㅠ)

 

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~