[백준] 11054 - 가장 긴 바이토닉 부분 수열

1. 문제

11054번: 가장 긴 바이토닉 부분 수열

2. 개요

수열 S가 어떤 수 Sk를 기준으로

$
S1 < S2 < … Sk-1 < Sk > Sk+1 > … SN-1 > SN
$

을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

주어진 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 dp 문제.

3. 풀이 및 코드

3-1. 풀이

주어진 수열을 수열 A라고 하자.

바이토닉 수열은,

인덱스 i까지의 오름차순 부분수열 + 인덱스 i+1 부터의 내림차순 부분수열로 나타낼 수 있다.

여기서 인덱스 i+1 부터의 내림차순인 부분수열은,

다시 수열 A를 뒤집은 수열 B의 인덱스 i-1까지의 오름차순인 부분수열이라고 할 수 있다.

위 결과들을 dp테이블로 저장한 뒤 더해 결과를 출력한다.

3-2. Python

import sys

N = int(sys.stdin.readline())

nums = list(map(int, sys.stdin.readline().split()))
nums2 = nums[::-1]

dpasc = [1 for _ in range(N)]
dpdesc = [1 for _ in range(N)]

for i in range(N):
    for j in range(i):
        if nums[i] > nums[j]:
            dpasc[i] = max(dpasc[i], dpasc[j] + 1)
        if nums2[i] > nums2[j]:
            dpdesc[i] = max(dpdesc[i], dpdesc[j] + 1)

ans = 0

for i in range(N):
    ans = max(ans, dpasc[i] + dpdesc[N-i-1] - 1)

print(ans)

3-3. C#

static void Main(string[] args)
{
    int N = int.Parse(Console.ReadLine());

    int[] nums = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    int[] nums2 = nums.Reverse().ToArray();

    int[] dpasc = new int[N];
    Array.Fill(dpasc, 1);

    int[] dpdesc = new int[N];
    Array.Fill(dpdesc, 1);

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (nums[i] > nums[j])
                dpasc[i] = Math.Max(dpasc[i], dpasc[j] + 1);
            if (nums2[i] > nums2[j])
                dpdesc[i] = Math.Max(dpdesc[i], dpdesc[j] + 1);
        }
    }

    int answer = 0;

    for (int i = 0; i < N; i++)
        answer = Math.Max(dpasc[i] + dpdesc[N - i - 1] - 1, answer);

    Console.WriteLine(answer);
}