C# 1149번 RGB거리

문제

코드 :

using System;
namespace PracticeAlgo
{
    class Program
    {
        static int N;
        static int[,] ColorCost;
        static int[,] totalCost;
        static void Main(string[] args)
        {
            {
                N = int.Parse(Console.ReadLine());
                //현재 비용 배열
                ColorCost = new int[N, 3];
                //최소 비용 저장 배열
                totalCost = new int[N, 3];
                for (int n = 0; n < N; n++)
                {
                    var buf = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
                    //2차원배열 채우기
                    ColorCost[n, 0] = buf[0];
                    ColorCost[n, 1] = buf[1];
                    ColorCost[n, 2] = buf[2];
                }
                for (int i = 0; i < N; i++)
                {
                    if (i == 0)
                    {
                        totalCost[i, 0] = ColorCost[i, 0];
                        totalCost[i, 1] = ColorCost[i, 1];
                        totalCost[i, 2] = ColorCost[i, 2];
                    }
                    else
                    {
                        //0 = R, 1 = G, 2 = B 일때
                        //R를 고른다면 이전 G과 B중에 최소값과 현재 R값을 더한다.
                        //위 과정을 R,G,B 모두에게 실행한다.
                        totalCost[i, 0] = Math.Min(totalCost[i - 1, 1], totalCost[i - 1, 2]) + ColorCost[i, 0];
                        totalCost[i, 1] = Math.Min(totalCost[i - 1, 0], totalCost[i - 1, 2]) + ColorCost[i, 1];
                        totalCost[i, 2] = Math.Min(totalCost[i - 1, 0], totalCost[i - 1, 1]) + ColorCost[i, 2];
                    }
                }
                Console.WriteLine(Math.Min(totalCost[N - 1, 0], Math.Min(totalCost[N - 1, 1], totalCost[N - 1, 2])));
            }
        }
    }
}

문제 풀이 :

처음에 그때그때마다 가장 작은 수를 고르면 될 줄 알았다. 그래서 코드를 아래와 같이 짰었다.

using System;
using System.Numerics;
using System.Linq;
namespace _6
{
    class Program
    {
        static int N = Convert.ToInt32(Console.ReadLine());

        static int sum = 0;
        static int index = -1;
        static int indextemp = 0;
        static bool[] isUsed = new bool[3];
        static int[,] rgbArr = new int[N, 3];
        static string RGBString;
        static string[] arr;
        static int[] temp;

        static public void RGB()
        {
            if(index != Array.IndexOf(temp, temp.Min()))
            {
                sum += temp.Min();
                index = Array.IndexOf(temp, temp.Min());
                return;
            }
            else
            {
                temp[Array.IndexOf(temp, temp.Min())] = 1000;
                RGB();
            }    
            
        }
        static void Main(string[] args)
        {
            for (int i = 0; i < N; i++)
            {
                RGBString = Console.ReadLine();
                arr = RGBString.Split(' ');
                temp = Array.ConvertAll(arr, int.Parse);
                RGB();
            }
            Console.WriteLine(sum);
        }
    }
}

그러나 이럴 경우 예제 입력 5의 경우 정확한 답이 나오지 않음을 알게 되었다.

여러가지 인터넷을 공부해서 알게된 점은 그리디처럼 그때그때마다 가장 최적의 수를 찾는 것이 아니라 R,G,B중 어느 곳을 골랐을 때 다음 선택에 영향을 생각해야만 한다. 이에 따라 수정했다.