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

정보

문제 바로가기 [클릭]

난이도: Gold3

관련 개념: #다이나믹 프로그래밍

---

조건

시간 제한	메모리 제한
1 초	256 MB

---

문제

수열 S가 어떤 수 S_k를 기준으로 S₁ < S₂ < … S_k-1 < S_k > S_k+1 > … S_N-1 > S_N을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {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를 이루고 있는 A_i가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ A_i ≤ 1,000)

---

출력

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

---

예제 입출력 1

입력

10
1 5 2 1 4 3 4 5 2 1

출력

7

---

힌트

예제의 경우 {1 5 2 1 4 3 4 5 2 1}이 가장 긴 바이토닉 부분 수열이다.

---

코드(파이썬)

n = int(input())
array = list(map(int, input().split()))
dp = [1]
dp2 = [1]

for i, num in enumerate(array[1:], 1):
    dp.append(max([dp[j] if array[j] < num else 0 for j in range(i)])+1)

array = array[::-1]
for i, num in enumerate(array[1:], 1):
    dp2.append(max([dp2[j] if array[j] < num else 0 for j in range(i)])+1)

print(max([dp[i]+dp2[n-i-1] for i in range(n)]) - 1)

---

특이사항

• 풀이방법
  • 이전에 학습한 LIS 알고리즘을 사용함
  • 주어진 숫자 리스트를 시작에서 차례대로 가장 긴 증가 부분수열을 dp 리스트에 저장
  • 주어진 숫자 리스트를 끝에서 거꾸로 가장 긴 증가 부분수열을 dp2 리스트에 저장
  • dp2 리스트를 뒤집으면 해당 숫자에서 가장 긴 감소 부분수열을 얻을 수 있음
  • dp1과 뒤집은 dp2를 더한 값 중 최대 값에서 해당 숫자가 2번 포함되어있으므로 1을 빼면 가장 긴 바이토닉 부분 수열 계산 완료
• 내 코드(30,864KB, 172ms)에 비해 우수한 코드(바로가기, 152,408KB, 1,212ms)와 비교

  • from collections import deque
    
    n = int(input())
    A = list(map(int, input().split()))
    result1 = []
    result2 = deque()
    dp1 = [0] * 1001
    dp2 = [0] * 1001
    
    for i in A:
        tmp = max(dp1[:i]) + 1
        dp1[i] = tmp
        result1.append(tmp)
    
    for i in A[::-1]:
        tmp2 = max(dp2[:i]) + 1
        dp2[i] = tmp2
        result2.appendleft(tmp2)
    
    sol = 0
    for i in range(len(result1)):
        sol = max(sol, result1[i] + result2[i])
    print(sol - 1)
    

  • 동일한 풀이이지만 기존보다 간단한 구현이 보임
  • 최적화하는 방법을 더 공부할 필요성이 있음

---

참고문헌

-