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

문제번호: 2096

문제명: 내려가기

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

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

 

오늘은 dp문제인 '내려가기' 문제를 풀었습니다. 3개의 숫자로 이루어진 배열이 n줄 주어졌을 때, 바로 위의 숫자를 선택하거나 바로 위 숫자와 바로 인접한 숫자를 선택하며 내려가는 숫자의 최대 합, 최소 합을 구하는 문제입니다.

dp[i, j]에서 선택할 수 있는 경우의 수는 바로 위, 위에 인접한 숫자를 선택하는 경우입니다. 이때 i는 3으로 고정된 값이므로

dpMax[0, i] = Math.Max(dpMax[0, i - 1], dpMax[1, i - 1]) + NumberPad[0, i]; // 왼쪽
dpMax[1, i] = Math.Max(dpMax[0, i - 1], Math.Max(dpMax[1, i - 1], dpMax[2, i - 1])) + NumberPad[1, i]; // 가운데
dpMax[2, i] = Math.Max(dpMax[2, i - 1], dpMax[1, i - 1]) + NumberPad[2, i]; // 오른쪽

 

위와 같이 점화식을 세웠습니다. 시간복잡도는 O(n^2) 입니다. (최소값 구하기도 동일.)
다음은 정답코드입니다.

 

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

    int n = int.Parse(sr.ReadLine());
    int[,] NumberPad = new int[3, n];

    for (int i = 0; i < n; i++)
    {
        int[] nums = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
        NumberPad[0, i] = nums[0];
        NumberPad[1, i] = nums[1];
        NumberPad[2, i] = nums[2];
    }

    int[,] dpMax = new int[3, n];
    dpMax[0, 0] = NumberPad[0,0];
    dpMax[1, 0] = NumberPad[1,0];
    dpMax[2, 0] = NumberPad[2,0];

    int[,] dpMin = new int[3, n];
    dpMin[0, 0] = NumberPad[0, 0];
    dpMin[1, 0] = NumberPad[1, 0];
    dpMin[2, 0] = NumberPad[2, 0];


    for (int i  = 1; i < n; ++i) // 최대
    {
        dpMax[0, i] = Math.Max(dpMax[0, i - 1], dpMax[1, i - 1]) + NumberPad[0, i]; // 왼쪽
        dpMax[1, i] = Math.Max(dpMax[0, i - 1], Math.Max(dpMax[1, i - 1], dpMax[2, i - 1])) + NumberPad[1, i]; // 가운데
        dpMax[2, i] = Math.Max(dpMax[2, i - 1], dpMax[1, i - 1]) + NumberPad[2, i]; // 오른쪽
    }

    for (int i  = 1; i < n; ++i) // 최소
    {
        dpMin[0, i] = Math.Min(dpMin[0, i - 1], dpMin[1, i - 1]) + NumberPad[0, i]; // 왼쪽
        dpMin[1, i] = Math.Min(dpMin[0, i - 1], Math.Min(dpMin[1, i - 1], dpMin[2, i - 1])) + NumberPad[1, i]; // 가운데
        dpMin[2, i] = Math.Min(dpMin[2, i - 1], dpMin[1, i - 1]) + NumberPad[2, i]; // 오른쪽
    }

    sw.Write(Math.Max(dpMax[0, n - 1], Math.Max(dpMax[1, n - 1], dpMax[2, n - 1])) + " "); // 최대
    sw.Write(Math.Min(dpMin[0, n - 1], Math.Min(dpMin[1, n - 1], dpMin[2, n - 1]))); // 최소
}