[알고리즘 문제 풀기] RGB거리 2(17404)

1. 문제 풀이 아이디어

• 다이나믹 프로그래밍을 활용해 시작 색상을 기준으로 각 집의 색상을 선택하며 인접한 집끼리 색이 겹치지 않도록 최소 비용을 계산하고, 첫 번째 집과 마지막 집의 색상이 같지 않은 경우 중 최솟값을 구한다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int n = int.Parse(sr.ReadLine());
    int[,] rgb = new int[n, 3];
    int[,,] dp = new int[n, 3, 3];

    for (int i = 0; i < n; i++)
    {
        string[] split = sr.ReadLine().Split();
        for (int j = 0; j < 3; j++)
        {
            rgb[i, j] = int.Parse(split[j]);
        }
    }
    dp[1, 0, 0] = 1000000;
    dp[1, 0, 1] = rgb[0, 0] + rgb[1, 1];
    dp[1, 0, 2] = rgb[0, 0] + rgb[1, 2];
    dp[1, 1, 0] = rgb[0, 1] + rgb[1, 0];
    dp[1, 1, 1] = 1000000;
    dp[1, 1, 2] = rgb[0, 1] + rgb[1, 2];
    dp[1, 2, 0] = rgb[0, 2] + rgb[1, 0];
    dp[1, 2, 1] = rgb[0, 2] + rgb[1, 1];
    dp[1, 2, 2] = 1000000;

    for (int s = 0; s < 3; s++)
    {
        for (int i = 2; i < n; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                int p1 = j == 0 ? j + 2 : j - 1;
                int p2 = j == 2 ? j - 2 : j + 1;
                dp[i, s, j] = Math.Min(dp[i - 1, s, p1], dp[i - 1, s, p2]) + rgb[i, j];
            }
        }
    }
    int result = int.MaxValue;
    for (int s = 0; s < 3; s++)
    {
        for (int j = 0; j < 3; j++)
        {
            if (s == j) continue;
            result = Math.Min(result, dp[n - 1, s, j]);
        }
    }
    sw.WriteLine(result);
}

3. 정리

• rgb[i, j]는 i번째 집을 j색으로 칠할 때의 비용이다.

• dp[i, s, j]는 시작 색상이 s일 때 i번째 집을 j색으로 칠했을 때의 최소 비용이다.

• 2번째 집부터 n-1번째 집까지 색이 겹치지 않게 이전 값을 참조하여 최소값을 누적한다.

• 마지막 집이 시작 색상과 같지 않은 경우 중 최소값을 정답으로 출력한다.