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

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

 

 

11053번 응용 문제이다.

어렵사리 풀긴 했는데, 인터넷에 많이들 푼 방법과는 조금 다르다.

역시 알고리즘 풀 때는 뒤집어서 생각해볼 필요가 있는 것 같다.

 

내가 푼 방법은 다음과 같다.

바이토닉 수열 길이를 bitonicSize에 각각 증가하고 있는 사이즈, 감소하고 있는 사이즈를 넣고

for문 내부에서는 현재 보고 있는 숫자 이전의 수열들을 하나하나 검사했다.

 

케이스를 2가지로 나눠서 어떤 경우에 그렇게 될 수 있는지, 그에 대한 결과가 어떻게 되어야 하는지 생각해봤다.

 

1. 현재 보고 있는 숫자(now)가 이전 숫자(before)보다 큰 경우는

- 계속 증가하고 있던 수열의 경우이거나

- 새로 시작하는 수열의 경우이다. 그렇다면

-> bitonicSize에서 증가하는 수열의 사이즈를 upBitonicSize에 집어넣는다.

 

2. 현재 보고 있는 숫자(now)가 이전 숫자(before)보다 작은 경우

- 계속 감소하고 있던 수열의 경우이거나,

- 증가하고 있다가 이번에 새로 감소하는 경우이다. 그렇다면

-> bitonicSize에서 둘 중에 큰 것을 downBitonicSize에 집어넣는다.

 

 

사실 이게 맞는 건지 잘 모르겠다.

설명하기 어려운 걸 보면, 이상한 알고리즘일지도 모르겠다. ㅜㅜ

 

앞에서부터, 뒤에서부터 수열을 세는 방법으로 다시 풀어봐야겠다.

import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
UP, DOWN = 0, 1
bitonicSize = [[1, 1]]  # [증가중인 바이토닉 사이즈, 감소중인 바이토닉 사이즈]

for now in range(1, N):  # now: 현재 보고 있는 숫자
    upBitonicSize = [0]  # 이전 수열들의 바이토닉 사이즈를 저장할 공간
    downBitonicSize = [0]
    for before in range(now):  # before: 이전 수열들
        if A[before] < A[now]:
            upBitonicSize.append(bitonicSize[before][UP])
        elif A[before] > A[now]:
            downBitonicSize.append(max(bitonicSize[before][UP], bitonicSize[before][DOWN]))
    bitonicSize.append([max(upBitonicSize)+1, max(downBitonicSize)+1])

maxValue = 0
for i in bitonicSize:
    maxValue = max(maxValue, i[0], i[1])

print(maxValue)