백준 11054 풀이 (가장 긴 바이토닉 부분 수열, 다이나믹 프로그래밍)

이번에는 저번 시간에 풀었던 11053을 응용한 문제를 풀어보자. 처음 보면 솔직히 나야 역시나 무슨 말인지 몰라서 2~3번은 더 읽어보았다. 

간단히 요약하자면  S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN 과 같은 수열의 형태인 바이토닉 부분 수열을 찾되 가장 긴 부분 수열을 찾아보자는 것이다.

 

11053번에서 나는 오름차순으로 가장 긴 부분 수열을 찾을 수 있었다. 11054는 내림차순을 구해보라는 문제이다. 일단 문제를 풀기에 앞서 표를 그리며 생각해본다.

number	1	5	2	1	4	3	4	5	2	1
dp (->)	1	2	2	...	.....	...	4	5	2	1
dp2 (<-)	1	5	2	....	....	...	3	3	2	1
total	1	6	3	...	...	...	6	7	3	1

dp는 왼쪽에서부터 하나씩 최장 증가 수열을 구한다. 그와 동시에 dp2는 오른쪽에서부터 최장 증가 수열을 구한다.

그러면 각 dp와 dp2의 값을 더하면 number값을 기준으로 오름차순과 내림차순의 최장 수열을 동시에 구할 수 있다.

 

n = int(input())
nl = list(map(int, input().split()))

dp = [0 for i in range(n)]
dp2 = [0 for i in range(n)]

for target in range(0,len(nl)):
    if dp[target] == 0 :
        dp[target] +=1
    for i in range(0,target):
        if nl[i] < nl[target]:
            if dp[i] + 1 > dp[target]:
                dp[target] = dp[i] + 1
    target2 = len(nl) - target - 1
    if dp2[target2] == 0:
        dp2[target2] += 1
    for i in range(len(nl)-1,target2,-1):
        if nl[i] < nl[target2]:
            if dp2[i] + 1 > dp2[target2]:
                dp2[target2] = dp2[i] + 1
print(dp)
for i in range(len(dp)):
    dp[i] += dp2[i] - 1
print(max(dp))