백준 C# 1916 내려가기

 

기존 완전탐색으로 진행하였으나.. 메모리 초과

최대 400만 바이트의 사용이 가능하기에, 모든 경우의 수를 배열에 저장하면 안된다...

 

접근

주어진 배열에서 최대[최소] 값을 선택하는 과정
선택은 현재 배열이 아닌 다음으로  입력된 배열이 기존에 있는 최적의 값에서 선택하는 것

 

입력된 순서대로 현재 배열[0]에서 다음 배열[1]의 값을 선택했을 경우에는
저장된 배열의 위치[0]에서 다음 수를 선택할 수 없는[2] 오류가 발생했다.

코드

internal class E1916_내려가기
{
    static void Main(string[] args)
    {
        string[] input(StreamReader s) => s.ReadLine().Split();

        using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
        {
            int iter = int.Parse(input(sr)[0]);

            //저장
            int[] Max = new int[3];
            int[] Min = new int[3];

            Max  = Array.ConvertAll(input(sr), int.Parse);
            Min = Max;

            for (int i = 1; i < iter; i++)
            {
                int[] arr = Array.ConvertAll(input(sr), int.Parse);

                int[] MAXA = new int[2] { Max[0], Max[1] };
                int[] MAXC = new int[2] { Max[1], Max[2] };

                Max = new int[] { arr[0] + MAXA.Max(), arr[1]+ Max.Max(), arr[2]+ MAXC.Max()};


                int[] MINA = new int[2] { Min[0], Min[1] };
                int[] MINC = new int[2] { Min[1], Min[2] };

                Min = new int[] { arr[0] + MINA.Min(), arr[1]+Min.Min(), arr[2]+ MINC.Min()};
            }

            Console.WriteLine($"{Max.Max()} {Min.Min()}");
        }
    }
}