백준 11054번 : 가장 긴 바이토닉 부분 수열 [C#]

1. 수열에서 어떤 인덱스까지의 가장 긴 증가하는 수열을 찾는 방법은?

> 증가하는 수열을 만들 때 어떤 수를 넣는 것이 최종적으로 맞는 것인지 아닌지를 깔끔한 공식으로 판단하기는 불가능하고, 모든 케이스를 비교해봐야한다.

> 0번 인덱스부터 재귀를 돌며 수열에서 왼쪽 숫자가 오른쪽 숫자보다 작다는 조건 아래에서 이 숫자를 수열에 넣는다, 안 넣는다로 다음 재귀를 돌리면서 가장 긴 수열을 찾는다. >> 2의 n제곱만큼의 시간이 걸림.

 

2. 비교를 하되, 중복을 줄일 수 있는 방법이 있을까?

> 특정 인덱스 i에서 선택지는 앞에서 만들어진 수열에 i번 숫자를 넣는다와 넣지 않는다로 나뉜다.

> 넣는다면 마지막 숫자가 i번 숫자보다 작은 수열 중 가장 긴 수열에 넣는 것이고

> 넣지 않는다면 이전 수열 i번 숫자가 가장 작아서 i번부터 새 수열을 시작하는 것이다.

이 방법으로 0번부터 n번까지 진행하면 각 인덱스에서 가장 긴 수열을 얻을 수 있고, 그 중 최댓값을 찾는다.

 

2-1. 한 단계씩 설명하면

> 0번 인덱스만 포함한 수열의 크기는 1이다. << 자기 자신부터 시작하는 수열의 크기

> 다음 1번 인덱스에선 0번 숫자보다 1번 숫자가 큰지, 0번까지의 수열에 1번을 추가할 지 말지를 본다.

> 다음 2번에선 같은 방법으로 비교 후, 0번까지의 수열, 1번까지의 수열 중 어느 것에 2번 숫자를 붙일 지 결정한다. 이건 루프를 돌며 각 인덱스의 수열길이를 기준으로 더 긴걸로 결정하면 된다. ex)  dp[2] = max( dp[0]+1, dp[2] ) >> dp[2] = max( dp[1]+1, dp[2] ) 

> 다음 3번에서도 같은 방법으로 비교, 인덱스에선 0,1,2번까지의 수열에 1번을 추가할지 말지를 본다.

이것은 i번째 인덱스에 i번째 숫자가 j보다 큰지 확인하고 j번째까지의 수열에 i번 숫자를 더할지 말지를 본다.

 

만약 4번 인덱스의 숫자가 아주 큰 수라면 4번의 수열의 크기는 이 수까지 포함하여 1이 증가하겠지만,

5번 인덱스의 숫자가 4번보다 작으면 4번 수열의 크기를 5번에서 사용할 수 없어서 3번까지중의 가장 긴 수열 선택할 것이다. 

따라서 각 인덱스의 숫자의 크기와 수열의 묶여있어서 큰 수가 배열에 섞이지 않으며 자연스럽게 그 인덱스에서의 최장 수열의 길이를 얻을 수 있다.

 

3. 여기까지가 가장 긴 수열이고, 가장 긴 바이토닉 수열은 이 과정을 양 끝에서 진행한 후 각 인덱스에서 앞에서 젠 수열의 길이와 뒤에서부터 젠 수열의 길이를 더한 것 중 가장 긴 것을 고르면 된다.

 

class Program
{
    static int[] nums;

    static int[] inc;
    static int[] dec;
    static int[] ans;


    static int n = 0;

    static void Main()
    {
        n = int.Parse(Console.ReadLine());
        string[] line = Console.ReadLine().Split();

        nums = new int[n + 1];

        for (int i = 0; i < n; i++)
        {
            nums[i] = int.Parse(line[i]);
        }

        inc = new int[n + 1]; // 앞
        dec = new int[n + 1]; // 뒤
        ans = new int[n + 1]; // 앞+뒤

        for (int i = 0; i < n; i++)
        {
            inc[i] = 1;
            dec[i] = 1;
        }

        // 앞에서부터
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[j] < nums[i])
                {
                    inc[i] = Math.Max(inc[i], inc[j] + 1);
                }
            }
        }

        // 뒤에서부터
        for (int i = n-1; i >= 0; i--)
        {
            for (int k = n - 1; k > i; k--)
            {
                if (nums[k] < nums[i])
                {
                    dec[i] = Math.Max(dec[i], dec[k] + 1);
                }
            }

            ans[i] = inc[i] + dec[i] - 1;
        }

        Console.Write(ans.Max());
    }
}