[17404] - RGB거리 2

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

17404번: RGB거리 2

 

 

문제풀이

RGB거리 문제(1149번)과 다르게 시작점의 색과 마지막점의 색이 달라야 된다. 즉, 시작점의 색을 정해주고, 끝점의 색이 시작점과 같지 않은것 중에 작은 것을 비교하면 된다.

 

1. R,G,B로 색이 총 3개이니 시작색을 각 1번씩, 3번 고정시켜주면 된다.

• 시작을 고정시킬 때는 한 값만 원래값으로, 나머지를 최대값+1인 1001로 설정시 최소값을 찾아야 되니 원래값이 들어간 것이 선택된다.

2. 현재색 + 이전에서 현재색이 아닌 다른 2색을 비교하여 누적시킨다.

3. 끝색이 R,G,B 3개로 나뉘어서 탐색이 되었으면, 시작색과 동일한 것을 제외하고 둘이 비교하여 정답에 작은값을 넣는다.

using System;
using System.Collections.Generic;
using System.Text;

namespace Baekjoon.Gold
{
    class _17404
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[][] rgb = new int[n][];
            for (int i = 0; i < n; i++)
                rgb[i] = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            int ans = int.MaxValue;
            int[,] color = new int[n, 3];
            //0 = 빨강, 1 = 초록, 2 = 파랑
            for (int idx = 0; idx < 3; idx++)
            {
                //시작 고정시키기
                for(int i = 0; i<3; i++)
                {
                    if (i == idx)
                        color[0, i] = rgb[0][i];
                    else
                        color[0, i] = 1001;
                }

                //dp탐색 -> 앞에꺼에서 작은거 + 색
                for (int i = 1; i < n; i++)
                {
                    color[i, 0] = Math.Min(color[i - 1, 1], color[i - 1, 2]) + rgb[i][0];
                    color[i, 1] = Math.Min(color[i - 1, 2], color[i - 1, 0]) + rgb[i][1];
                    color[i, 2] = Math.Min(color[i - 1, 1], color[i - 1, 0]) + rgb[i][2];
                }

                //답 도출
                for(int i = 0; i<3; i++)
                {
                    if (i != idx)
                        ans = Math.Min(ans, color[n - 1, i]);
                }
            }

            Console.WriteLine(ans);
        }
    }
}