해당 문제는 수열 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)
'Algorithm > Greedy' 카테고리의 다른 글
[이것이 코딩 테스트다, 그리디] 큰 수의 법칙 (0) | 2024.07.29 |
---|