[Baekjoon] 11054번 : 가장 긴 바이토닉 부분 수열 (Python)

[Baekjoon] 11054번 : 가장 긴 바이토닉 부분 수열 (Python)

 

목차

 

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

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

Python

 

방법 1 - 메모리 30864KB / 시간 456ms / 코드 길이 315B

 

이 문제를 풀기 어렵다면 한 방향을 고려한 비슷한 문제를 먼저 확인하길 바란다.

https://aigong.tistory.com/385

[Baekjoon] 11053번 : 가장 긴 증가하는 부분 수열 (Python)

 

11053번과 같이 11054번은 증가하는 부분에 대한 고려를 진행해야 한다.

다만 바이토닉 수열이라고 하여 점진적인 증가와 점진적인 감소가 최대가 되는 부분을 찾아야한다.

이에 대한 나만의 방법은 양방향에 대한 DP Memorization을 고려하는 것이다.

이를 위한 d1과 d2 list를 통한 DP Memorization을 진행한다.

d1에는 i번째의 값과 0~i-1번째의 값들 간의 비교를 진행하여 저장하고

d2에는 n-1-i번째의 값과 n-1~n-i번째의 값들 간의 비교를 진행한다.

예를 들어 주어진 예시에서는 10개의 숫자가 주어진다.

이때 i=2를 고려하면

d1은 2번째의 값과 0,1번째의 값들 간의 비교를 진행하여 최대값을 d1에 저장한다.

d2는 7번째의 값과 9,8번째의 값들 간의 비교를 진행하여 최대값을 d2에 저장한다.

 

이후 두 list를 더하고 최대가 되는 부분에서 -1한 값을 출력한다.

-1을 하는 이유는 중복된 중앙값 때문이다.

 

예제에 따르면 d1과 d2는 다음과 같이 도출된다.

 

# d1 : [1, 2, 2, 1, 3, 3, 4, 5, 2, 1]
# d2 : [1, 5, 2, 1, 4, 3, 3, 3, 2, 1]

 

n=int(input())
l=list(map(int, input().split()))
d1=[1]*n
d2=[1]*n
for i in range(1,n):
    for j in range(i):
        if l[i] > l[j]:
            d1[i]=max(d1[i], d1[j]+1)
        if l[n-1-i] > l[n-1-j]:
            d2[n-1-i] = max(d2[n-1-i], d2[n-1-j]+1)

for i in range(n):
    d1[i]=d1[i]+d2[i]
print(max(d1)-1)

 

 

방법 2 - 메모리 30864KB / 시간 244ms / 코드 길이 362B

 

방법 1에서 언급한 방법을 분리하여 진행한 결과이다.

또한 d1과 d2에 대한 위치별 비교를 추가하여 불필요한 계산을 회피한다. 

 

n=int(input())
l=list(map(int, input().split()))
d1=[1]*n
d2=[1]*n
for i in range(n):
    for j in range(i):
        if l[i] > l[j] and d1[i] <= d1[j]:
            d1[i]=d1[j]+1

for i in range(n-1,-1,-1):
    for j in range(i,n):
        if l[i] > l[j] and d2[i] <= d2[j]:
            d2[i] = d2[j] + 1

for i in range(n):
    d1[i]=d1[i]+d2[i]-1
print(max(d1))