[BOJ][C#] 11054 가장 긴 바이토닉 부분 수열

📕 문제

📌 링크

📗 접근 방식

입력 처리

• 수열의 길이 n을 입력받는다.
• 수열의 각 원소를 공백으로 구분하여 입력받는다.

LIS (최장 증가 부분 수열) 계산

• 이중 반복문을 사용하여 각 위치에서의 LIS 값을 계산한다.
  • dp[i, 0]은 해당 위치에서 왼쪽에서 오른쪽으로 가장 긴 증가하는 부분 수열의 길이를 나타낸다.
  • 수열의 각 원소에 대해 그 이전의 모든 원소들과 비교하여 더 긴 증가 부분 수열이 있다면 업데이트해준다.

LDS (최장 감소 부분 수열) 계산

• 반대로, 이중 반복문을 사용하여 각 위치에서의 LDS 값을 계산한다.
  • LIS와 마찬가지로 진행

최종 결과 계산

• 각 위치에서의 LIS와 LDS 값을 합쳐서 해당 위치를 포함한 바이토닉 부분 수열의 길이를 계산합니다.
• 이 중 가장 큰 값을 찾아 최종 결과로 출력합니다.

📘 코드

namespace BOJ
{
    class No_11054
    {
        static void Main()
        {
            int n = int.Parse(Console.ReadLine());
            int[] inputs = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int[,] dp = new int[n, 2];
            
            for (int i = 0; i < n; i++)
            {
                dp[i, 0] = 1;
                for (int j = 0; j <= i; j++)
                {
                    if (inputs[i] > inputs[j] && dp[i, 0] < dp[j, 0] + 1)
                    {
                        dp[i, 0] = dp[j, 0] + 1;
                    }
                }
            }
            
            for (int i = n-1; i >= 0; i--)
            {
                dp[i, 1] = 1;
                for (int j = n-1; j >= i; j--)
                {
                    if (inputs[i] > inputs[j] && dp[i, 1] < dp[j, 1] + 1)
                    {
                        dp[i, 1] = dp[j, 1] + 1;
                    }
                }
            }
            
            int answer = 0;
            for (int i = 0; i < n; i++)
            {
                int temp = dp[i, 0] + dp[i, 1] - 1;
                if (answer < temp)
                {
                    answer = temp;
                }
            }

            Console.WriteLine(answer);
        }
    }
}

📙 오답노트

역시 DP는 DP다...

📒 알고리즘 분류

• 다이나믹 프로그래밍