(Python/🥇5)백준알고리즘 11054번: 가장 긴 바이토닉 부분 수열

문제 바로가기

백준 가장 긴 바이토닉 부분 수열

문제 :

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다. 수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오

입려 :

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

출력 :

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

 

풀이 :

 

예제풀이로 설명을 하겠다 .

1 5 2 1 4 3 4 5 2 1

 

내가 생각한 아이디어는 각 idx 까지 왼쪽에서 오는 LIS 오른쪽에서 오는 LIS 의 합을 더해줘서 저장한다 였다.

예를 들면 

1   // 5 2 1 4 3 4 5 2 1
1 5 // 2 1 4 3 4 5 2 1

이런식으로 말이다. 그래서 처음에 id값을 저장해서 해야하나 싶었지만 리스트 reverse 하고나서 구하면 된다.

 

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

N = int(sys.stdin.readline())
lst = [int(i) for i in sys.stdin.readline().split(" ")]
dp_max = [1] * N
dp_min = [1] * N
left = []

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

res = 0
for i in range(N):
    res = max(res,dp_max[i]+dp_min[i])
print(res-1)

 

max는 왼쪽 min은 오른쪽이다.

 

max는 평소 알고있는 LIS 를 사용해서 해주고

그다음은 min인데 원래 기존의 리스트를 뒤집어준다.

그러고 LIS 를 해주면  (9), (9,8),(9,8,7) 이런식으로 뒤에서 올라가는 수열을 저장할수 있다.

이것을 dp_min에 저장하는데 이것을 그냥 사용하면 안된다.

왜냐하면 지금 dp_max 에는 [0,1,2,3,4,5,6,7,8,9,9] 까지의 각각의 최댓값이  들어있다.

근데 여기에 dp_min을 더해주면 

 

res에 처음에 dp_max[0] 과 dp_min[0] 인데 이거를 인덱스로하면 0번과 10번을 더하는것이다,

dp_min 에는 반대로 저장되어있기 때문에 그래서 뒤집어준다.

 

그렇게 되면 포문 돌때 [0],[9~0] // [0,1],[9~1] 이런식으로 들어간다.

인덱스 값이 두 번 들어가기때문에 -1 을 해줘야한다