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

 

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

문제



 

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

---

풀이

기본적인 풀이방법은 11053번 "가장 긴 증가하는 부분수열" 문제와 아주 유사하다.

 

먼저 가장 긴 증가하는 부분수열의 알고리즘인 LIS 알고리즘에 따라 기존 수열의 LIS값을 DP1 배열에 저장한다.

for i in range(N):
    for j in range(i):
        if S[i] > S[j]:
            dp1[i] = max(dp1[i], dp1[j] + 1)

이렇게 하면 예제의 수열이 다음과 같이 저장된다

Index	1	5	2	1	4	3	4	5	2	1
DP1	1	2	2	1	3	3	4	5	2	1

 

DP1수열이 LIS의 값이 된다. 즉 증가하는 부분수열의 값이 되는 것이다.

 

하지만 우리는 감소하는 부분수열 또한 구해야 하기 때문에 또 다른 방법을 사용해야 한다.

 

감소하는 부분수열을 구하기 위해서는

기존에 수열의 값을 뒤집은 뒤 LIS 알고리즘을 적용시켜 DP2에 저장한 후 DP2를 다시 뒤집으면 된다!

S.reverse()
for i in range(N):
    for j in range(i):
        if S[i] > S[j]:
            dp2[i] = max(dp2[i], dp2[j] + 1)
dp2.reverse()

해당 코드를 거친 후 배열의 값은 다음과 같다.

Index	1	5	2	1	4	3	4	5	2	1
DP2	1	5	2	1	4	3	3	3	2	1

 

따라서 DP1과 DP2에 같은 인덱스값을 더하면 그것이 해당 수열의 바이토닉 수열 길이값이 된다.

이 때 더한값에서 -1을 해주어야 하는데 그 이유는 최대값 (증가와 감소의 경계값)이 중복돼서 더해지기 때문이다.

ansList = []
for i in range(N):
    ansList.append(dp1[i] + dp2[i])

print(max(ansList) - 1)

 

최종적으로 더한값의 최대값을 출력한다.

 

코드

N = int(input())

S = list(map(int, input().split()))
dp1 = [1] * N
dp2 = [1] * N

for i in range(N):
    for j in range(i):
        if S[i] > S[j]:
            dp1[i] = max(dp1[i], dp1[j] + 1)

S.reverse()
for i in range(N):
    for j in range(i):
        if S[i] > S[j]:
            dp2[i] = max(dp2[i], dp2[j] + 1)
dp2.reverse()

ansList = []
for i in range(N):
    ansList.append(dp1[i] + dp2[i])

print(max(ansList) - 1)