[백준] 11055, 11054

가장 큰 증가 부분 수열 (11055번)

• 사이트/난이도: 백준 / 실버2
• 코드

# 실버2 가장 큰 증가 부분 수열
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
dp = a[:]

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

• 느낀점
  • dp 대표 문제인 증가하는 수열 문제와 알고리즘은 같다.
  • 다만 i의 값이 j보다 클 때 dp를 i인덱스 까지의 최대값 으로 활용하면 된다.

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

• 사이트/난이도: 백준/ 골드 4
• 코드

# 골드4 가장 긴 바이토닉 부분 수열
import sys
input = sys.stdin.readline

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

increase = [1] * n
for i in range(1, n):
    for j in range(i):
        if a[i] > a[j]:
            increase[i] = max(increase[i], increase[j] + 1)

a.reverse()
decrease = [1] * n
for i in range(1, n):
    for j in range(i):
        if a[i] > a[j]:
            decrease[i] = max(decrease[i], decrease[j] + 1)
decrease.reverse()

answer = 0
for i in range(n):
    answer = max(answer, increase[i] + decrease[i])
print(answer - 1)

• 느낀점
  • 가장 긴 증가하는 부분수열과 가장 긴 감소하는 부분 수열을 합친 문제
  • 바이토닉 수열은 증가하는 수열과 감소하는 수열 중 둘을 합칠때 가장 큰 값의 인덱스가 바이토닉 수열이 된다.