[BOJ/백준] 2491번 수열 (Python 파이썬)

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

2491번: 수열

 

문제

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 

9
1 2 2 4 4 5 7 7 2

예제 출력 1 

8

예제 입력 2 

9
4 1 3 3 2 2 9 2 3

예제 출력 2 

4

예제 입력 3 

11
1 5 3 6 4 7 1 3 2 9 5

예제 출력 3 

2

 

---

풀이

해당 문제의 경우 "증가하는 수열"과 "감소하는 수열"을 모두 구해야 합니다. 따라서 둘을 분리해서 각각을 구해주었습니다.

증가하는 수열의 경우, "앞선 값 >= 현재 값" 이면 현재의 개수에서 1을 더해서 앞에다가 넣어주면 됩니다.

for i in range(N-1):
    if data[i+1] >= data[i]:
        dp[i+1] += dp[i]

감소하는 수열은 그 반대입니다.

for i in range(N-1):
    if data[i+1] <= data[i]:
        dp2[i+1] += dp2[i]

 

 

최종적인 구현은 아래와 같습니다.

Code

import sys
input = sys.stdin.readline
N = int(input())
data = list(map(int, input().split()))
dp = [1]*N
dp2 = [1]*N
for i in range(N-1):
    if data[i+1] >= data[i]:
        dp[i+1] += dp[i]
for i in range(N-1):
    if data[i+1] <= data[i]:
        dp2[i+1] += dp2[i]
max1 = max(dp)
max2 = max(dp2)
print(max(max1, max2))