[백준알고리즘/11054번/파이썬] 가장 긴 바이토닉 수열

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

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

 

문제: 가장 긴 바이토닉 부분 수열을 출력하는 문제

 

풀이 방법: 다이나믹 프로그래밍

 

풀이 코드:

import sys

n = int(input())
array = list(map(int,sys.stdin.readline().rstrip().split()))

dp = [1]*(n+1)
af = [1] *(n+1)

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

for i in range(n-1,-1,-1):
    for k in range(n-1,i-1,-1):
        if array[i] > array[k] and af[k] >= af[i]:
            af[i] = af[k] + 1

for i in range(n+1):
    dp[i] += af[i]

print(max(dp)-1)

 

풀이 설명:

결국은 바이토닉 수열이란 1 < k < n 을 만족하는 숫자 k,n 이 있을 때   1 ~ k번째 수까지 오름차순, k ~ n번째 수까지는 내림차순이 되는 수열을 말합니다.

 

따라서 저는 k번째 수가 있을 때,

k번째 수까지 구할 수 있는 오름차순 수열의 최대 길이를 구하고

수열 끝에서부터 k번째 수 까지 역순으로 보았을 때 만들 수 있는 오름차순 수열의 최대 길이를 구한 다음 두 값을 더하는 방식으로 코드를 구현하였습니다.

dp = [1]*(n+1)
af = [1] *(n+1)

 

먼저, k번째 수로 만들 수 있는 수열의 길이를 저장하기 위해 1로 초기화한 array를 만듭니다.

1로 초기화한 이유는 1개의 수로 길이가 1인 수열을 만들 수 있기 때문입니다.

 

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

array[ i ]로 만들 수 있는 최대 길이의 오름차순 길이는 array[ i ] 보다 작은 수 중 제일 큰 수로 만들 수 있는 길이의 + 1 입니다.

 

따라서, i 번째 수로 만들 수 있는 수열의 값을 구하기 위해 0 ~ i -1 번째 까지 탐색하여 array[ i ] 보다 작은 수를 찾고 그 작은 수로 만들 수 있는 수열의 길이가 array[ i ] 번째 수로 만들 수 있는 수열의 같거나 길 경우 +1 을 하여 dp에 저장해줍니다.

 

이렇게 되면, 다음과 같이 동작되게 됩니다.

10	20	30
1	1	1

10	20	30
1	2	1

10	20	30
1	2	3

 

i = 0 일 때, 제일 앞 노드이므로 아무런 동작이 일어나지 않습니다.

i = 1 일 때, 앞에 10인 노드가 있으므로 [10, 20]인 길이가 2짜리 수열을 만들 수 있습니다.

따라서 array[1] > array[0] 가 성립하고, dp[0] >= dp[1]이 성립하므로 dp[1] = dp[0] + 1  = 2도 성립합니다.

 

i = 2일 때는 다음과 같습니다.

먼저 j = 0일 때, 10을 만나게 되면 30 > 10이고 , dp[0]  > = dp[2] 이므로  dp[2] = 2가 됩니다.

[ 10, 30 ]인 수열을 만들 수 있으므로 맞죠.

 

j = 1일 때, 20을 만나게 되면 30 > 20이고, dp[1] >= dp[2] 이므로 dp[2] = 3이 됩니다.

즉, 최종적으로 [10,20,30] 인 수열로 만들 수 있는 오름차순 수열의 최대 길이를 구하게 됩니다.

 

 

 

 

for i in range(n-1,-1,-1):
    for k in range(n-1,i-1,-1):
        if array[i] > array[k] and af[k] >= af[i]:
            af[i] = af[k] + 1

 

수열 [30,20,10] 이 있으면 10 -> 30 으로 가는 방향으로 오름차순 수열 길이를 계산하는 코드입니다.

역순으로 탐색했을 뿐 원리는 위와 같습니다.

 

for i in range(n+1):
    dp[i] += af[i]

print(max(dp)-1)

 

10 20 30 20 10 이란 수열이 있을 때,

dp에는 10 20 30을 의미하는 값인 3이 저장되어있을 것이고

마찬가지로 af에도 30 20 10을 의미하는 값인 3이 저장되어 있을 것입니다.

그럼 30이 이중으로 세어진 것이므로 최대 값에 -1을 더해준 값을 출력해줍니다.