[백준] 17404 - RGB거리 2

1. 문제

17404번: RGB거리 2

2. 개요

N개의 집이 있고 각 집은 빨강, 초록, 파랑으로 칠할 수 있다.

이 때, 각 집은 바로 옆의 집과 색이 달라야만 한다. (1번 집과 마지막 집도 서로 달라야 한다.)

집 수 N과 각 집을 각 색으로 칠할 때의 비용이 주어졌을 때, 조건을 만족하며 모든 집을 색칠하는 최소 비용을 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

첫 집의 색을 먼저 정하고 dp로 풀어낸다.

마지막에 첫 집의 색과 같은 경우를 제외하고 answer와 비교해 갱신한 후 답을 출력한다.

3-2. Python

import sys

N = int(sys.stdin.readline().rstrip())

ans = 10000000
rgb = []
for i in range(N):
    rgb.append(list(map(int,sys.stdin.readline().split())))

for i in range(3):
    cost = [[10000000, 10000000, 10000000] for _ in range(N)]
    cost[0][i] = rgb[0][i]

    for j in range(1, N):
        cost[j][0] = rgb[j][0] + min(cost[j-1][1], cost[j-1][2])
        cost[j][1] = rgb[j][1] + min(cost[j-1][0], cost[j-1][2])
        cost[j][2] = rgb[j][2] + min(cost[j-1][0], cost[j-1][1])

    for j in range(3):
        if i != j:
            ans = min(ans, cost[-1][j])

print(ans)

3-3. C#

internal class Program
{
    static void Main(string[] args)
    {
        int answer = 10000000;

        int N = int.Parse(Console.ReadLine());

        int[,] rgb = new int[N, 3];

        for (int i = 0; i < N; i++)
        {
            string[] input = Console.ReadLine().Split();
            rgb[i, 0] = int.Parse(input[0]);
            rgb[i, 1] = int.Parse(input[1]);
            rgb[i, 2] = int.Parse(input[2]);
        }

        for (int i = 0; i < 3; i++)
        {
            int[,] cost = new int[N, 3];
            cost[0, 0] = 10000000;
            cost[0, 1] = 10000000;
            cost[0, 2] = 10000000;
            cost[0, i] = rgb[0, i];

            for (int j = 1; j < N; j++)
            {
                cost[j, 0] = rgb[j, 0] + Math.Min(cost[j - 1, 1], cost[j - 1, 2]);
                cost[j, 1] = rgb[j, 1] + Math.Min(cost[j - 1, 0], cost[j - 1, 2]);
                cost[j, 2] = rgb[j, 2] + Math.Min(cost[j - 1, 0], cost[j - 1, 1]);
            }

            for (int j = 0; j < 3; j++)
            {
                if (i != j)
                {
                    answer = Math.Min(answer, cost[N - 1, j]);
                }
            }
        }

        Console.WriteLine(answer);
    }
}