문제 링크

가장 긴 바이토닉 부분 수열

문제 설명

바이토닉 수열이란, 길이 N의 수열 $S$의 특정 수 $S_k$를 기준으로

$S_1<S_2<...<S_{k-1}<S_k<S_{k+1}<...<S_N$

를 만족하는 수열을 의미한다.
수열이 주어졌을때, 해당 수열내의 가장 긴 바이토닉 부분 수열을 구하시오.

문제 풀이

테스트케이스의 수열

1 5 2 1 4 3 4 5 2 1

의 경우에 가장 긴 바이토닉 부분 수열은 특정 수 5를 기준으로 한

1 2 3 4 5 2 1

이다.

이 문제는 가장 긴 부분 수열 LIS를 2번 적용하면 빠르게 풀 수 있다.

1. 특정 수 i를 기준으로 수열을 seq[:i+1]과 sep[i:] 두개로 나눈다.
   
2. 나눈 두개의 seq에 대해 각각 LIS를 돌린다.
   -> 여기서 seq2는 바이토닉 조건의 $S_k<S_{k+1}<...<S_N$ 에 해당하므로 reverse후 LIS를 돌린다.
3. 2에서 구한 두 리스트의 LIS를 더한 후 중복 카운트된 부분(A[i])을 빼준다.

코드

import sys
import copy

input = sys.stdin.readline

N = int(input())
seq = list(map(int, input().split()))
answer = 0

for k in range(N):
    seq1 = copy.deepcopy(seq[:k+1])
    seq2 = copy.deepcopy(seq[k:])
    seq2.reverse()
    dp1 = [1]*(len(seq1)+1)
    dp2 = [1]*(len(seq2)+1)

    #LIS 알고리즘
    for i in range(1, len(seq1)):
        for j in range(0, i):
            if seq1[j] < seq1[i]:
                dp1[i] = max(dp1[i], dp1[j]+1)

    #LIS 알고리즘
    for i in range(1, len(seq2)):
        for j in range(0, i):
            if seq2[j] < seq2[i]:
                dp2[i] = max(dp2[i], dp2[j]+1)
    answer = max(answer, max(dp1)+max(dp2)-1)

print(answer)

느낀점

LIS를 안다면 쉽게 접근해서 풀 수 있는 문제인것같다. 근데 나는 아직 LIS를 완벽하게 이해 못하고 코드만 외워서릐,,,,,, 날잡고 LIS 공부하고 LIS 문제집 한번 풀어봐야겠음!

그리구 골드됐다 ㅎㅎ, ,, , ,