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

문제번호: 1932

문제명: 정수 삼각형

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

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

 

오늘은 트리와 재귀 문제를 풀었습니다. 처음엔 깊이 기반 완전탐색으로 문제풀이를 시도해봤는데 시간초과로 인해 실패했습니다. 따라서 대안으로 memo배열을 사용하여 이미 계산한 부분에 대해서는 다시 계산하는 일이 없도록 계산횟수를 줄여 시간초과에 걸리지 않을 수 있었습니다.
다음은 정답코드입니다.

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

    List<int[]> list = new List<int[]>();

    int n = int.Parse(sr.ReadLine());
    for (int i = 0; i < n; i++)
    {
        int[] input = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
        list.Add(input);
    }

    int?[,] memo = new int?[n, n];

    int DFS(int depth, int index)
    {
        if (depth == n - 1)
            return list[depth][index];

        if (memo[depth, index] != null)
            return memo[depth, index].Value;

        int left = DFS(depth + 1, index);
        int right = DFS(depth + 1, index + 1);

        memo[depth, index] = list[depth][index] + Math.Max(left, right);

        return memo[depth, index].Value;
    }

    int answer = DFS(0, 0);
    sw.WriteLine(answer);

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