[C#] 백준 1149번 문제풀이

문제번호: 1149

문제명: RBG거리

문제링크: https://www.acmicpc.net/problem/1149

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다.

 

오늘은 다이나믹 프로그래밍 실버 1 문제를 풀어보았습니다. 3가지 규칙에 따라 최소비용으로 건물을 칠하는 문제입니다. 이중배열로 dp테이블, 비용테이블을 만들어서 비용 테이블을 참조해서 dp테이블을 채워갔고 dp테이블 마지막줄에 3개의 값 중에서 가장 작은 값을 구해 출력해주었습니다. 시간 복잡도는 O(1)입니다.

다음은 정답코드입니다.

 

public static void Main()
{
    using var sr = new StreamReader(Console.OpenStandardInput());
    using var sw = new StreamWriter(Console.OpenStandardOutput());

    int N = int.Parse(sr.ReadLine());
    int[,] cost = new int[N, 3]; // 비용
    int[,] dp = new int[N, 3]; // 테이블

    for (int i = 0; i < N; i++) // 입력 비용배열에 기입
    {
        int[] input = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
        for (int j = 0; j < 3; j++)
            cost[i, j] = input[j];
    }

    for (int c = 0; c < 3; c++) // 초기값 기입
        dp[0, c] = cost[0, c];

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

    }

    int answer = Math.Min(dp[N - 1, 0], Math.Min(dp[N - 1, 1], dp[N - 1, 2])); // 마지막 디피줄 값중에 가장 작은 값
    sw.WriteLine(answer);

    sr.Close();
    sw.Close();
}