[1932] 정수 삼각형

생각

재귀함수로 풀려고 생각하고 있었는데 생각해보니 그러면 시간초과가 난다.
따라서 동적 계획 방법으로 구현하려고 한다.
여기서, 있는 그대로 7->3, 8 -> 8, 1, 0->..이런 식으로 하면 매번 인덱스의 값이 정상범위인지 조건을 확인해주기가 번거롭다.
따라서, n*n배열이 아닌, n+1 * n+1 배열로 하여, 어차피 빈 곳은 0이기 때문에
1번 인덱스들 부터 실제 값으로 채워주고 max여부를 판단해주면 일일이 인덱스 확인을 해주지 않아도 된다.

위쪽의 부모 노드의 값을 비교하여, 큰 부모의 값을 가져와 자식노드의 값과 합치는 식으로 하면 된다.

이후, n번째 줄에서 (1부터 시작하니 n-1이 아니라 n이다) 최댓값을 구해주면 된다.

처음 코드

namespace SongE
{
    public class Program
    {
        static void Main(string[] args)
        {   
            int n = Convert.ToInt32(Console.ReadLine());
            int[,] a = new int[n + 1, n + 1];
            for (int i = 1; i <= n; i++)
            {
                string[] arrInput = Console.ReadLine().Split();
                for (int j = 1; j <= i; j++)
                    a[i, j] = Convert.ToInt32(arrInput[j - 1]);
            }

            for(int i = 2; i <= n; i++)
            {
                for(int j = 1; j <= i; j++)
                {
                    a[i, j] += Math.Max(a[i - 1, j - 1], a[i - 1, j]); 
                }
            }

            int max = 0;
            for(int i = 1; i <= n; i++)
            {
                max = max > a[n,i] ? max : a[n,i];
            }

            Console.WriteLine(max);
        }
    }
}

이쪽은 더 간결하게 가변배열을 이용해서 Max 메서드를 이용한 ver

namespace SongE
{
    public class Program
    {
        static void Main(string[] args)
        {   
            int n = Convert.ToInt32(Console.ReadLine());
            //int[,] a = new int[n + 1, n + 1];
            int[][] a = new int[n + 1][];
            for (int i = 1; i <= n; i++)
            {
                string[] arrInput = Console.ReadLine().Split();
                a[i] = new int[n + 1];
                for (int j = 1; j <= i; j++)
                    a[i][j] = Convert.ToInt32(arrInput[j - 1]);
            }

            for(int i = 2; i <= n; i++)
            {
                for(int j = 1; j <= i; j++)
                {
                    a[i][j] += Math.Max(a[i - 1][j - 1], a[i - 1][j]); 
                }
            }

            Console.WriteLine(a[n].Max());
        }
    }
}