[백준 - C#] 1149번 RGB거리

문제링크

https://www.acmicpc.net/problem/1149

1149번: RGB거리

 

문제

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

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

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

조건

시간제한 : 0.5초
메모리 제한 : 128 MB

입력

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

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

문제정리

1. 연속적으로 같은색이 나올 수 없습니다.
2. 모든 집을 칠하는 최소비용을 구해야합니다.

이번 문제의 경우 모든 집을 색칠 할 때 드는 최소 비용을 구하는 문제입니다.

색은 총 레드 그린 블루가 있으며 같은 색을 연속적으로 칠할 수 없습니다. 

이번 문제도 DP로 풀어야 했으며 고민 하던 중 모든 경로의 경우의 수를 찾아 최솟값을 찾아야한 다는것을 느꼈습니다.

 

N번째 레드집을 칠할 때 N-1 번째 집 그린과 블루 중 비용이 적은 것을 선택하여 최소비용을 구하고

그린과 블루를 똑같이 최소비용을 구하여 마지막에 최종 최소비용을 구하면 됩니다.

 

점화식으로는 아래와 같습니다.

레드는 dp[N, 0] = Min (dp[N-1, 1], dp[N-1,2]) + cost[N,0] 
그린은 dp[N, 1] = Min (dp[N-1, 0], dp[N-1,2]) + cost[N,1] 
블루는 dp[N, 2] = Min (dp[N-1, 0], dp[N-1,1]) + cost[N,2] 

해당 점화식을 이용하여 아래의 코드를 확인해보면 좋을 것 같습니다.

 

C# 코드

static void Main(string[] args)
{
    StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
    StreamReader reader = new StreamReader(Console.OpenStandardInput());
 
    int N = int.Parse(reader.ReadLine());
 
    int[,] dp = new int[N + 1, 3];
 
    dp[0, 0] = 0;
    dp[0, 1] = 0;
    dp[0, 2] = 0;
 
    for (int i = 1; i <= N; i++)
    {
        int[] input = Array.ConvertAll(reader.ReadLine().Split(), int.Parse);
 
        // i번째 집이 Red일 경우
        dp[i, 0] = Math.Min(dp[i - 1, 1], dp[i - 1, 2]) + input[0];
 
        // i번째 집이 Green일 경우
        dp[i, 1] = Math.Min(dp[i - 1, 0], dp[i - 1, 2]) + input[1];
 
        // i번째 집이  Blue일 경우
        dp[i, 2] = Math.Min(dp[i - 1, 0], dp[i - 1, 1]) + input[2];
    }
 
    // 최소비용
    writer.WriteLine(Math.Min(dp[N, 0], Math.Min(dp[N, 1], dp[N, 2])));
 
    writer.Close();
    reader.Close();
}

읽어주셔서 감사합니다 오늘도 즐거운 하루 되세요.