백준 - 가장 긴 증가하는 부분 수열, 가장 긴 바이오닉 부분 수열(11053, 11054 파이썬 풀이)

먼저 비교적 쉬운 문제인 가장 긴 증가하는 부분 수열 문제는 한 수열에서 부분적으로 증가하는 수열을 찾고 그 중에 제일 긴 부분 수열을 찾는 문제이다.

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
dp = [0 for i in range(n)]
for i in range(n):
    for j in range(i):
        if a[i] > a[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1
print(max(dp))

dp라는 배열을 먼저 선언해준 뒤 반복문을 통해 증가하는 부분 수열을 모두 구해준다.

이중 포문을 사용하는 이유는 현재 계산 중인 배열에 해당 조건에 맞는다면 이전에 있는 것을 더해주고 안쪽 포문을 

나가면서 현재 계산 중인 수에 대해 +1을 해주고 이것을 반복해준다.

이 문제는 위의 문제였던 가장 긴 증가하는 부분 수열을 활용한 문제인데 쉽게 알고리즘을 생각하면 위에서 구한 증가하는 부분 수열의 가장 긴 길이와 증가하는 부분 수열의 가장 긴 길이를 기준으로 반대로 돌려 감소하는 부분 수열의 길이를
구하면 되는 문제이다.

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
dp = [0 for _ in range(n)]
dpr = [0 for _ in range(n)]


for i in range(n):
	for j in range(i):
		if a[i] > a[j] and dp[i] < dp[j] :
			dp[i] = dp[j]
	dp[i] +=1

for i in range(n-1, -1, -1):
	for j in range(n-1, i, -1):
		if a[i] > a[j] and dpr[i] < dpr[j] :
			dpr[i] = dpr[j]
	dpr[i] +=1
a=0
for i in range(n):
	a=max(a, dp[i] + dpr[i] - 1)
print(a)

증가하는 가장 긴 부분 수열과 앞 수열을 기준으로 감소하는 가장 긴 부분 수열을 구해 합쳐 주었고 그것의 최대 값을
구했다.