백준 11054 파이썬
https://www.acmicpc.net/problem/11054
11054번: 가장 긴 바이토닉 부분 수열
첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)
www.acmicpc.net
이번 문제는 이전에 풀었던 [CS/알고리즘] - 백준 11053 파이썬 - 가장 긴 증가하는 부분 수열 - 동적 계획법, LIS 문제의 응용이다. 바이토닉 부분 수열을 가장 긴 증가하고 감소하는 부분 수열이다. 즉 이전에 풀었던 LIS 문제에서 배열의 각 위치에서의 최대 증가하는 부분 수열을 주어진 배열과 주어진 배열을 뒤집은 배열 2가지를 구해서 해결할 수 있다.
Python 풀이
import sys
read = sys.stdin.readline
N = int(read())
A = list(map(int, read().split()))
forward = [0] * N
backward = [0] * N
def calc(reverse=False):
if reverse:
temp = [A[-1]]
seq = backward
r = range(N-1, -1, -1)
else:
temp = [A[0]]
seq = forward
r = range(N)
for i in r:
if temp[-1] < A[i]:
temp.append(A[i])
else:
idx = 0
for j in range(len(temp)):
if temp[j] < A[i]:
idx += 1
else:
temp[idx] = A[i]
break
seq[i] = len(temp)
calc()
calc(True)
res = -1
for i in range(N):
res = max(res, forward[i] + backward[i])
print(res-1)
- calc 함수는 LIS를 구하는 함수이다.
- reverse flag를 사용하면 배열을 뒤에서부터 순회해서 가장 긴 감소하는 부분 수열을 구할 수 있다.
- 각각 증가하고 감소하는 부분 수열을 구하고 같은 위치의 값을 더한 값 중 최대값이 가장 긴 바이토닉 수열이 된다.
- 위치가 겹쳐 중복되는 1을 빼줘야한다.
댓글0