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

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

 

www.acmicpc.net

---

🤔 문제 설명

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

 

🤨 제한 사항

• 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

• 첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

 

😀 입출력 예

입력	출력
10 1 5 2 1 4 3 4 5 2 1	7

 

👩‍🔧 사용 메서드 및 속성

sys.stdin.readline()	사용자로부터 한 줄의 입력을 받습니다.
split()	문자열을 나눠서 배열로 반환합니다.
append()	리스트 끝에 요소를 추가합니다.
map()	리스트의 각 요소를 지정된 함수로 처리해줍니다.

 

👩‍🏫 어떻게 풀어요?

 

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

 

저도 처음에는 이 문제를 한번에 풀려고 되게 생각을 많이 했어요. 어떻게 해야 메모이제이션 배열을 선언하고, 어떤 수를 기준으로 잡아야지 상승하다가 하강 혹은 하강 혹은 상승 하는 수열의 길이를 구할 수 있는지를요.

 

일단, 어떤 수를 기준으로 잡아야 하긴 하는데 그 수열의 최대값이나 최소값을 기준으로 잡으면 안되겠죠?

왜냐하면

 

1 2 5 4 10 1 10 5 4 3 2 1

 

이런 경우도 있을 수 있고, 수열의 모든 값이 같은 경우도 있을 수 있으니까요. 

 

그래서 어떤 수를 기준으로 잡고 풀기에는 너무 어려운 문제입니다. 기준이 명확하지 않으니까요.

그러다가 문득, 어떤 아이디어가 머리를 스쳐갔죠

 

가장 긴 수열을 동적 프로그래밍 기법을 사용해 정방향에서 찾고, 역방향에서 찾으면 풀리지 않을까?

 

 

 

정방향으로 가장 긴 수열을 찾으면 [1, 2, 3, 4, 5,]가 나오고 총 길이는 5네요!

 

역방향으로 가장 긴 수열을 찾으면 [1, 2, 3, 4, 5,]가 나오고 총 길이는 5네요!

 

vscode로 코드를 돌리면~

 

이렇게 결과가 나옵니다!

저는 메모이제이션 1 배열에는 정방향을, 메모이제이션 2 배열에는 역방향의 가장 긴 수열의 길이를 넣었습니다.

그런데 문제가 있습니다.

 

 

아무리 봐도 2개를 더했을 때 최대값은 8인데요?

 

당연히 8이 나오죠!

왜냐하면 정방향과 역방향의 최대 길이를 보면

 

[1, 2, 3, 4, 5]

[5, 4, 3, 2, 1]

 

이렇게 최대 값이 중첩되어 있기 때문이죠.

그래서 각자 더해서 최대값을 구하고, 거기다가 - 1을 해주면 답을 쉽게 구할 수 있답니다.

 

 

 

 

 

 

 

 

👾트리스티의 답

import sys
 
n = int(sys.stdin.readline().split()[0])
arr = list(map(int, sys.stdin.readline().split()))
memo = [1 for _ in range(n)]
memo2 = [1 for _ in range(n)]
numArr = []
 
def alg(memo) :
 
    for i in range(1, len(arr)) :
        for j in range(0, i) :
            if arr[i] > arr[j] :
                memo[i] = max(memo[i], memo[j] + 1)
 
    for i in range(len(arr) - 1, -1, -1) :
        for j in range(len(arr) - 1, i, -1) :
            if arr[i] > arr[j] :
                memo2[i] = max(memo2[i], memo2[j] + 1)
    
 
    for i in range(len(arr)) :
        numArr.append(memo[i] + memo2[i] - 1)
    return max(numArr)
print(alg(memo))

 

※ 잘못된 정보가 있거나 수정사항이 있다면 댓글로 남겨주세요!