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

문제

https://www.acmicpc.net/problem/11054
백준 단계별 풀이 - 동적 계획법 1

---

풀이

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

 

즉, 수열에서 어느 한 지점을 P라고 했을때 (증가하는 수열), P, (감소하는 수열)형태가 되어야 한다.

아하, 이해는 쉽지만... 구현이 어렵다!
결국 구글링, AI를 통해 풀이를 얻어냈다.

 

찾아보니 바이토닉 수열을 구하는 공식은 아래와 같다.
바이토닉 수열 = LIS(증가부분수열) + LDS(감소부분수열) - 1

 

하지만 우리는 전환점이 되는 지점을 모르는 상태다.
무조건 LIS, LDS를 구하는게 아니라 수열 하나하나를 전환점으로 가정하고 따져봐야한다.

 

예시 데이터로 살펴보면,
{1 5 2 1 4 3 4 5 2 1}에서 가장 바이토닉 수열은 {1 2 3 4 5 2 1}, 길이는 7이다.
이건 뒤에서 세번째의 5를 전환점으로 삼았을때의 LIS+LDS-1 값이다.

 

정답 코드는 아래와 같다.

# 메모리: 31252KB / 시간: 100ms

from sys import stdin


input = stdin.readline
N = int(input())
A = list(map(int, input().split()))

def bitonic():
    lis = [1] * N
    lds = [1] * N

    for i in range(1, N):  # LIS
        for j in range(i):
            if A[i] > A[j] and lis[i] < lis[j] + 1:
                lis[i] = lis[j] + 1

    for i in range(N-2, -1, -1):  # LDS
        for j in range(N-1, i, -1):
            if A[i] > A[j] and lds[i] < lds[j] + 1:
                lds[i] = lds[j] + 1

    max_length = 0
    for i in range(N):
        max_length = max(max_length, lis[i] + lds[i] - 1)

    return max_length

print(bitonic())

1. 입력값 할당

from sys import stdin


input = stdin.readline
N = int(input())
A = list(map(int, input().split()))

2. 부분 수열을 구할 함수 작성

def bitonic():
    lis = [1] * N
    lds = [1] * N

    for i in range(1, N):  # LIS
        for j in range(i):
            if A[i] > A[j] and lis[i] < lis[j] + 1:
                lis[i] = lis[j] + 1

    for i in range(N-2, -1, -1):  # LDS
        for j in range(N-1, i, -1):
            if A[i] > A[j] and lds[i] < lds[j] + 1:
                lds[i] = lds[j] + 1

lis와 lds에 1로 이루어진 N만큼의 리스트를 할당해줬다.
각 인덱스값은 i번째 원소까지의 LIS, LDS 값을 뜻한다.

 

첫번째 for문으로 LIS를 구하고, 두번째 for문으로 LDS를 구해준다.

i는 1부터 N-1번째 인덱스를, j는 i이전까지의 인덱스를 탐색한다.
만약 A의 i번째 인덱스값 > j번째 인덱스값이고, i의 현재 LIS값보다 j의 LIS값+1이 더 크다면 lis[j]+1로 변경한다.

 

예시 데이터로 살펴보자.
A = [1, 5, 2, 1, 4]이고, lis = [1, 1, 1, 1, 1]일때의 과정이다.

먼저 i = 1일때 j = 0만 가능하다.
A[i]는 5, A[j]는 1이므로 첫번째 조건은 만족한다.
lis[i]는 1, lis[j]도 1이므로 lis[i] < lis[j] + 1 조건도 만족한다.
따라서 lis[i]값을 2로 설정한다. lis = [1, 2, 1, 1, 1]

i = 2일때, j = 0, 1 이다.
A[i]는 2, A[j]는 각각 1, 5이므로 j가 1일때 첫번째 조건을 만족한다.
lis[i]는 1, lis[j]은 2이므로 lis[i] < lis[j] + 1 조건도 만족.
lis = [1, 2, 3, 1, 1]

 

...

이런식으로 진행하며 LIS값을 구해준다.

 

다음은 LDS인데, 그냥 뒤에서부터 LIS를 구하는 방식으로 작성했다.
증가수열을 뒤집으면 감소수열이 되므로 상관없다.

i는 N-2번째 인덱스(뒤에서 2번째)부터 0번째 인덱스까지 1씩 줄어든다.
과정은 위와 같다.

    max_length = 0
    for i in range(N):
        max_length = max(max_length, lis[i] + lds[i] - 1)

    return max_length

LIS, LDS를 구했으면 최대 바이토닉 수열을 구해줄 차례다.

최대값(=결과값)을 넣어줄 함수 max_length를 선언하고 0을 할당해준다.(또는 float("-inf"))
0부터 N-1까지 모든 인덱스를 순회하며,
현재까지의 max_length값과 바이토닉 수열 공식(lis + lds - 1)을 대입한 값을 비교한다.

 

모든 비교를 마치고 최대값을 return한다.

3. 결과 출력

print(bitonic())

위 함수를 실행한 결과를 그대로 출력한다.
return값으로 max_length, 최대값이 반환되므로 그대로 실행+출력 해주면 된다.