2022.02.06 [백준] C# RGB거리

 

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

1149번: RGB거리

 

---

풀이

이 문제는 이전의 집과 같은 색으로 칠하지 않으면서 최소한의 비용으로 칠할 때 총 비용을 구하는 문제이다. 

모든 경우의 수를 따져 가면서 이미 거친 경우를 다시 계산하지 않기 위해 메모이제이션을 이용하여 각 경우의 수마다 배열에 저장하였다.

a가 0일 때, 첫 집을 칠할때의 각 색의 가격이 totalCost가 된다. 그 다음부터 각 컬러의 상황에서 이전 집을 칠할때의 최소 totalCost를 Math.Min으로 뽑아내고 현재 컬러에 대한 비용을 더했다.

using System;
using System.Text;
using System.IO;
 
class Program
{
    static int[,] colorCost;
    static int[,] totalCost;
    static void func(int a)
    {
        if (a == 0)
        {
            totalCost[0, 0] = colorCost[0, 0];
            totalCost[0, 1] = colorCost[0, 1];
            totalCost[0, 2] = colorCost[0, 2];
        }
        else
        {
            totalCost[a, 0] = Math.Min(totalCost[a - 1, 1], totalCost[a - 1, 2]) + colorCost[a, 0];
            totalCost[a, 1] = Math.Min(totalCost[a - 1, 0], totalCost[a - 1, 2]) + colorCost[a, 1];
            totalCost[a, 2] = Math.Min(totalCost[a - 1, 0], totalCost[a - 1, 1]) + colorCost[a, 2];
        }
    }
    static void Main()
    {
        StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
        StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
        StringBuilder sb = new StringBuilder();
        int n = int.Parse(sr.ReadLine());
        colorCost = new int[n, 3];
        totalCost = new int[n, 3];
        for(int i = 0; i < n; i++)
        {
            var num = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
            colorCost[i, 0] = num[0];
            colorCost[i, 1] = num[1];
            colorCost[i, 2] = num[2];
            func(i);
        }
        sw.WriteLine(Math.Min(totalCost[n-1, 0], Math.Min(totalCost[n-1, 1], totalCost[n-1, 2])));
        sr.Close();
        sw.Close(); 
    } 
}

 

아래 코드는 totalCost없이 colorCost에 바로 이전의 비용과 자신의 비용을 더해주었다.

using System;
using System.Text;
using System.IO;
 
class Program
{
    static int[,] colorCost;
    static void func(int a)
    {
        
 
        colorCost[a, 0] = Math.Min(colorCost[a - 1, 1], colorCost[a - 1, 2]) + colorCost[a, 0];
        colorCost[a, 1] = Math.Min(colorCost[a - 1, 0], colorCost[a - 1, 2]) + colorCost[a, 1];
        colorCost[a, 2] = Math.Min(colorCost[a - 1, 0], colorCost[a - 1, 1]) + colorCost[a, 2];
        
    }
    static void Main()
    {
        StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
        StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
        StringBuilder sb = new StringBuilder();
        int n = int.Parse(sr.ReadLine());
        colorCost = new int[n, 3];
        var num = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
        colorCost[0, 0] = num[0];
        colorCost[0, 1] = num[1];
        colorCost[0, 2] = num[2];
        for (int i = 1; i < n; i++)
        {
            var num1 = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
            colorCost[i, 0] = num1[0];
            colorCost[i, 1] = num1[1];
            colorCost[i, 2] = num1[2];
            func(i);
        }
        sw.WriteLine(Math.Min(colorCost[n - 1, 0], Math.Min(colorCost[n - 1, 1], colorCost[n - 1, 2])));
        sr.Close();
        sw.Close();
    }
}