[백준알고리즘] 11054번: 가장 긴 바이토닉 부분 수열 -Python

[백준알고리즘] 11054번: 가장 긴 바이토닉 부분 수열 -Python

https://www.acmicpc.net/problem/11054

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

밑에 새로 풀면서 추가 설명을 적어놨다. 첫 풀이가 어려우면 밑의 풀이를 보면 된다.

2019-08-13

첫 번째 풀이

LIS(Longest Increasing Subsequence)의 응용문제 중 하나이다.

문제를 보면 뽑아낸 부분수열이 증가하다가 감소하는 형태를 가질 때의 최대길이를 구하는 문제이다.

쉬운 버전인 11053번의 경우 증가하는 수열의 최대길이만 구하면 됐기 때문에 각 값마다 해당 값이 포함되는 길이의 max를 넣어주었고, 최종적으로 값들의 max값들을 비교해서 구했었다.

 

이 문제도 마찬가지이지만 증가와 감소를 나눠서 생각해야 한다.

하지만 이 문제는 11053번 문제를 풀었던 방법과 달리 값들마다의 max값들을 넣어서는 비교할 수 없는 문제이다.

예시로 다음과 같은 숫자열이 존재한다고 가정하자

1 5 2 3 4 5 3 2 1

이 수열에서 값 '5'가 포함되는 증가수열의 최대의 길이는 'max(2, 5) = 5'가 된다.

마찬가지로 '5'가 포함되는 감소 수열의 최대 길이는 'max(5, 4) = 5'가 된다.

따라서 최대 '5'가 포함되는 바이토닉 부분 수열의 최대 길이는 '5 + 5 - 1 = 9'가 되지만 실제로는

1 5 2 3 4 5 3 2 1

위와 같은 부분 수열로 최대 길이가 8이기 때문이다.

 

여기서 말하는 감소 수열이란 증가수열의 반대이다. 증가 수열은 왼쪽에서 시작하는 LIS라고 보면, 감소 수열은 오른쪽에서 시작해서 1씩 인덱스를 감소시키면서 구하는 LIS이다. 직관적으로 보기위해 감소 수열이라고 붙였다.

 

각 '값'에다가 길이를 비교할 수 없기 때문에 이번에는 각 '인덱스'마다 길이를 비교하도록 했다.

기본 아이디어는 똑같다. 각 인덱스가 포함되는 부분 수열의 최대 증가 수열의 길이와 최대 감소 수열의 길이를 구한 다음, 합한 후 1을 빼주는 방식이다.

위의 예시를 사용하면 다음과 같다.

 

기본 수열 : 1 5 2 3 4 5 3 2 1

증가 길이 : 1 2 2 3 4 5 3 2 1

감소 길이 : 1 5 2 3 4 4 3 2 1

길이의 합 : 2 7 4 6 8 9 6 4 2

결과 ===> 1 6 3 5 7 8 5 3 1

 

기본 아이디어는 쉬웠기 때문에 다음에 코드를 보이면 다음과 같다.

import sys


N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
increase = [1 for _ in range(N)]
decrease = [1 for _ in range(N)]
result = [0 for _ in range(N)]

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

# decrease
for i in range(N-1, -1, -1):
    for j in range(i + 1, N):
        if A[i] > A[j] and decrease[i] < decrease[j] + 1:
            decrease[i] = decrease[j] + 1
    result[i] = decrease[i] + increase[i] - 1

print(max(result))

 

2020-02-12 (추가)

두 번째 풀이

그냥 한 번 더 풀어보다가 이전의 설명이 너무 어려워 보여서 추가하게 되었다 ㅎㅎ;;

 

이중 for문을 두 번 사용해서 오른쪽에서부터 증가와 왼쪽에서부터 증가(위에서는 감소라고 작성)하는 길이를 각각 구한 것은 동일하다.

 

오른쪽으로 증가하는 수열의 길이를 구하기 위해서는 왼쪽부터 하나씩 인덱스를 늘려가며 이전에 자기보다 value는 작으면서 수열의 길이가 긴 경우 그 길이에 +1을 시켜 저장을 한다.

마찬가지로 왼쪽으로 증가하는(오른쪽으로 감소하는) 수열의 길이를 구하기 위해서 가장 오른쪽에서부터 하나씩 인덱스를 줄여가며 현재보다 큰 인덱스의 value가 작으면서 수열의 길이가 긴 경우 그 길이에 +1을 시켜주었다. 

 

그리고 이 증가하는 수열과 감소하는 수열을 operator 모듈의 add를 통해 두 리스트의 합을 구했다. 여기서 operator.add를 이용하면 수열 A = [a, b, c], 수열 B = [i, j, k]의 합인 [a+i, b+j, c+k]를 구할 수 있게 된다.

 

이렇게 두 리스트의 합을 구한 후 두 리스트의 합에서 가장 큰 값은 실제 길이를 구할 때에는 중복되어 더해지기 때문에 1을 빼주면 된다.

 

import sys
import operator

N  = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
inc = [1] * N
dec = [1] * N

for i in range(N):
    for j in range(i):
        if arr[i] > arr[j] and inc[i] <= inc[j]:
            inc[i] = inc[j] + 1

for i in range(N-1, -1, -1):
    for j in range(i, N):
        if arr[i] > arr[j] and dec[i] <= dec[j]:
            dec[i] = dec[j] + 1

sys.stdout.write(str(max(map(operator.add, inc, dec)) - 1))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다