[백준] 11054 가장 긴 바이토닉 부분 수열 풀이 - (python 파이썬)

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

사용 언어: Python 파이썬

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

이 문제는 가장 긴 증가하는 부분 수열 구하는 문제유형을 약간(?) 꼬아둔 문제다. 가장 긴 증가하는 부분 수열 구하기 유형을 처음 접한다면 이 글을 읽어보길 바란다.

2020/10/08 - [Algorithm] - 가장 긴 증가하는 부분 수열(LIS) 완전 정복 - 백준 파이썬

가장 긴 증가하는 부분 수열(LIS) 완전 정복 - 백준 파이썬

문제를 보면 다음과 같이 정의되어있다.

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 증가하는 수열과 감소하는 수열 두 가지로 나누어서 생각해보자

 

        주어진 수열:  1, 5, 2, 1, 4, 3, 4, 5, 2, 1

증가하는 수열 길이: 1, 2, 2, 1, 3, 3, 4, 5, 2, 1

감소하는 수열 길이: 1, 5, 2, 1, 4, 3, 3, 3, 2, 1

 

각 인덱스별로 증가하는 수열 길이 + 감소하는 수열 길이의 합이 가장 큰 지점이 바이토닉 수열의 Sk 원소가 된다.

즉, 주어진 수열에서의 바이토닉 수열은 1,2,3,4,5,2,1가 되며, Sk는 5가 된다.

증가하는 수열: 1,2,3,4,5

감소하는 수열: 5,2,1

합을 구하면서 주어진 수열의 8번째 원소인 5를 두 번 계산하였으므로 1을 빼주면 정답을 구할 수 있다.

 

x = int(input())

case = list(map(int, input().split()))
reverse_case = case[::-1]

increase = [1 for i in range(x)] # 가장 긴 증가하는 부분 수열
decrease = [1 for i in range(x)] # 가장 긴 감소하는 부분 수열(reversed)

for i in range(x):
    for j in range(i):
        if case[i] > case[j]:
            increase[i] = max(increase[i], increase[j]+1)
        if reverse_case[i] > reverse_case[j]:
            decrease[i] = max(decrease[i], decrease[j]+1)

result = [0 for i in range(x)]
for i in range(x):
    result[i] = increase[i] + decrease[x-i-1] -1

print(max(result))

내가 작성한 코드는 다음과 같다. 

가장 긴 증가하는 부분 수열을 계산하면서, 가장 긴 감소하는 부분 수열도 같이 알아내기 위해서 주어진 수열을 reverse 시켰다. 대신, decrease에는 인덱스가 반대로 들어가있으므로, 다시 한 번 바꿔서 생각해줘야한다.

 

이 방법이 헷갈린다면 for문을 역방향으로 돌려 가장 긴 감소하는 부분 수열을 구하는 방법도 있다.

x = int(input())

case = list(map(int, input().split()))

increase = [1 for i in range(x)]

for i in range(x):
    for j in range(i):
        if case[i] > case[j]:
            increase[i] = max(increase[i], increase[j]+1)

decrease2 = [1 for i in range(x)]
for i in range(x-1, -1, -1):
    for j in range(x-1, i, -1):
        if case[i] > case[j]:
            decrease2[i] = max(decrease2[i], decrease2[j]+1)

result = [0 for i in range(x)]
for i in range(x):
    result[i] = increase[i] + decrease2[i] -1 

print(max(result))

 

두 코드 다 통과했다 :)

LIS 관련 백준 문제들

이 문제를 풀었다면 연관된 다른 문제들도 풀어보면 좋을 것 같다.

11053번 11055번 11722번 12015번 12738번 14002번 14003번