[ 2491 ] [DP] 수열

문제 설명

---

문제

0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾아내어 그 길이를 출력하는 프로그램을 작성하라.

예를 들어 수열 1, 2, 2, 4, 4, 5, 7, 7, 2 의 경우에는 1 ≤ 2 ≤ 2 ≤ 4 ≤ 4 ≤ 5 ≤ 7 ≤ 7 이 가장 긴 구간이 되므로 그 길이 8을 출력한다. 수열 4, 1, 3, 3, 2, 2, 9, 2, 3 의 경우에는 3 ≥ 3 ≥ 2 ≥ 2 가 가장 긴 구간이 되므로 그 길이 4를 출력한다. 또 1, 5, 3, 6, 4, 7, 1, 3, 2, 9, 5 의 경우에는 연속해서 커지거나 작아지는 수열의 길이가 3 이상인 경우가 없으므로 2를 출력하여야 한다.

입력

첫째 줄에는 수열의 길이 N이 주어지고, 둘째 줄에는 N개의 숫자가 빈칸을 사이에 두고 주어진다. N은 1 이상 100,000 이하의 정수이다.

출력

첫째 줄에 가장 긴 길이를 출력한다.

---

풀이 과정

1. DP 테이블을 2개 구성한다 (증가, 감소)
   • up_dp, down_dp는 모두 기본값을 1로 구성한다(자기 자신만으로 구성된 수열의 길이:1)
   • seq[i] <= seq[i-1]인 경우 down_dp[i] = down_dp[i-1] + 1
   • seq[i] >= seq[i-1]인 경우 up_dp[i] = up_dp[i-1] + 1
2. 테이블을 모두 채웠으면 down_dp의 최댓값, up_dp의 최댓값중 큰 값을 리턴하면 된다.

---

소스 코드

import sys

input = sys.stdin.readline

n = int(input().rstrip())
sequence = list(map(int, input().rstrip().split()))

down_dp = [1] * n
up_dp = [1] * n

for i in range(1, n):
    if sequence[i-1] <= sequence[i]:
        up_dp[i] = up_dp[i-1] + 1
    if sequence[i-1] >= sequence[i]:
        down_dp[i] = down_dp[i-1] + 1

print(max(max(up_dp), max(down_dp)))