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

생성일

2024/08/19 03:29

태그

다이나믹 프로그래밍

URL

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

문제 설명

•

크기가 NNN인 수열에 대해 가장 긴 바이토닉 부분 수열의 길이를 구하는 문제

예제 입력/출력

•

입력1

Plain Text
복사

•

출력1

Plain Text
복사

제약 조건

•

1≤N≤1,0001 ≤ N ≤ 1,0001≤N≤1,000

•

1≤원소들의값≤1,0001 ≤ 원소들의 값 ≤ 1,0001≤원소들의값≤1,000

문제 풀이

풀이1 브루트 포스 - O(2N⋅N)O(2^{N} \cdot N)O(2N⋅N)

풀이2 그리디

풀이3 DP - O(N2)O(N^2)O(N2)

풀이 코드

•

Bottom-Up 방식의 구현

# input
N = int(input())
arr = [0] + list(map(int, input().split()))

# solve
dp1 = [0] * (N + 1)
dp2 = [0] * (N + 1)
dp1[1] = dp2[N] = 1

# dp1
for n in range(2, N + 1):
	dp1[n] = 1
	for i in range(1, n): # dp1[n] 갱신
		if arr[n] > arr[i]:
			dp1[n] = max(dp1[n], dp1[i] + 1)

# dp2
for n in range(N - 1, 0, -1):
	dp2[n] = 1
	for i in range(N, n, -1): # dp2[n] 갱신
		if arr[n] > arr[i]:
			dp2[n] = max(dp2[n], dp2[i] + 1)

ans = 0
for n in range(1, N + 1):
	ans = max(ans, dp1[n] + dp2[n] - 1)

print(ans)
Python
복사

Top-Down 방식의 구현