[백준] 4237: 비 단조성 (python 파이썬)

해당 문제는 수열 A가 주어졌을 때 원소들을 지우면서 "B[0] > B[1] < B[2] > B[3] < ..."를 만족하는 수열 중 가장 길이가 긴 수열을 구하는 문제다. 결국 ">"를 찾고, 다음 "<"를 찾고, ">"를 찾는 과정을 반복하면 문제를 해결할 수 있다. 이유는 다음과 같다. 

•  a > b < c < d > e: 이 경우  >, <, > 총 3번 반복했으므로 답은 4가 된다. b<c<d인 경우 b<d만 남기면 결국 d>e이기 때문에 a>b<d<e를 만족하여 길이가 4인 조건을 만족하는 수열을 찾을 수 있다.
• a > b < c > d > e < f: >, <, >, < 총 4번 반복했으므로 답은 5가 된다. c>d>e는 c>e만 남길 수 있다. 이때 b<c>e를 만족하고, e<f를 만족하기 때문에 a>b<c>e<f를 만족하여 길이가 5인 조건을 만족하는 수열을 찾을 수 있다. 

코드는 아래와 같이 작성할 수 있다.

import sys
input = sys.stdin.readline

testCase = int(input())
for i in range(testCase):
    values = list(map(int, input().split()))
    
    n = values[0]; sequence = values[1:]

    result = 0   
    
    # flag가 0인 경우 ">"를 찾고, 1인 경우 "<"를 찾도록 한다.
    flag = 0
    for i in range(0, n-1):
        if flag == 0 and sequence[i] > sequence[i+1]:
            flag = 1
            result += 1
        elif flag == 1 and sequence[i] < sequence[i+1]:
            flag = 0
            result += 1

    print(result+1)