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

문제

 

풀이

내 풀이

import sys

n = int(sys.stdin.readline())
seq = list(map(int, sys.stdin.readline().split()))

dp = [1] * n
for i, v in enumerate(seq):
    for j in range(i-1, -1, -1):
        if seq[j] < v:
            dp[i] = max(dp[i], dp[j]+1)

for i, v in enumerate(seq):
    for j in range(i-1, -1, -1):
        if seq[j] > v:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

이 문제는 이전에 풀었던 11053번 가장 긴 증가하는 부분 수열 문제에서 변형된 문제이다.

아이디어는 11053번 문제와 비슷하다.

 

먼저 알아보기 쉽게 점들로 표현해보자

먼저 증가하는 수열을 체크해보자

순서를 매기기 위해 현위치에서 0쪽으로 선형탐색한다는 것을 생각하고 보면 이해가 수월하다.

그 다음 감소하는 수열을 체크해보자

감소하는 수열 역시 순서를 현위치에서 0쪽으로 선형탐색하여 찾아 매긴다는 것을 생각하여 살펴보자

이렇게 증가하는 수열의 길이를 메모해놓고 감소하는 수열을 체크하여 메모된 값에 누적시키면 최대 길이를 찾을 수 있게 된다.

항상 max 값을 찾으려 하기 때문에 감소하는 수열 체크 시 7번을 확인해도 max(6, 7)이므로 7이 최대길이로 나오게 된다.

 

회고

직관적으로 바로 풀긴했지만, 이렇게 해결된 이유를 좀 더 찾아서 설명할 수 있도록 분석해봐야 될 것 같다.