뱅글뱅글 도는 탐험가의 경로가 중첩되는지? Q

탐험가가 북서남동(반시계방향으로) 주어진 배열의 길이만큼씩 계속 움직인다. 전부 움직이는 동안 한번이라도 본인의 경로를 밟는 경로가 있을까?

ex ) 2 1 1 2 >> cross(1)

1 2 3 4 >> not cross(0)

이건 빼박 성질탐구 문제네..

뭐 나이브하게는 경로를 기록해 두면서 밟는지 체크할 수 있겠지만, 메모리 사용이 과다하고

정답 요구사항은 싱글 패스, O(1) 메모리이므로 결국 성질탐구 뿐

대충 두가지 방법이 있는데, 안으로 줄어드는 경우와 밖으로 확산하는 경우가 있다. 두 경우에 대해 계속적으로 성립하는지 확인해 나가야 한다.

// There are only two patterns when cross can happen, 
        // one involves four moves another involves six moves. 
        // Checking for this patterns is sufficient.  
        // C#
        static void Main(string[] args)
        {
            //double[] n = new double[] { 2, 2, 2, 1 }; // No cross
            //double[] n = new double[] { 2, 2, 2, 2 }; // Cross
            //double[] n = new double[] { 3, 2, 2, 3 }; // Cross
            //double[] n = new double[] { 3, 3, 2, 2, 3 }; // Cross
            //double[] n = new double[] { 2, 2, 4, 5, 1, 4 }; // No Cross
            //double[] n = new double[] { 2, 2, 4, 5, 3, 4 }; // Cross
            //double[] n = new double[] { 1, 2, 4, 5, 1, 4 }; // No Cross
            double[] n = new double[] { 0.5, 2, 2, 4, 5, 3, 4, 0.5 }; // Cross

            for (int i = 0; i < n.Length; i++)
            {
                if (i >= 3 && 
                    n[i] >= n[i - 2] &&
                    n[i - 1] <= n[i - 3])
                {
                    Console.WriteLine("Cross Detected, pattern #1");
                    return;
                }
                if (i >= 5 &&
                    n[i] >= n[i - 2] - n[i - 4] &&
                    n[i - 2] >= n[i - 4] &&
                    n[i - 1] >= n[i - 3] - n[i - 5] &&
                    n[i - 3] >= n[i - 5])
                {
                    Console.WriteLine("Cross Detected, pattern #2");
                    return;
                }
            }
            Console.WriteLine("No Cross");
        }