[Python] 2491번 수열

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

2491번: 수열

---

 

22/09/12

 

 

이 문제 또한 그룹 채점 현황에서 있는 무작위의 문제를 골라서 푼 문제이다.

---

 

문제 접근 방식:

 

 

전형적인 DP문제인데, 나는 DP리스트를 2개로 세웠다.

 

DP1은 가장 긴 감소하는 수열, DP2는 가장 긴 증가하는 수열의 DP리스트이다.

 

나는 DP1[i]를 i번째 원소까지 보았을 때, 가장 긴 감소하는 연속된 수열의 길이라고 정의했다.

 

일단 전부 1로 초기화를 하고, 반복문을 사용하여 DP리스트를 업데이트하는 형식으로 문제를 풀었다.

 

그렇다면, 만약 수열 A[i] <= A[i-1]이라면 연속된 숫자이면서 이후 숫자가 더 작은 것이므로, DP1[i] = DP1[i-1] + 1을 해주었다.

 

그렇지 않다면, 연속된게 끊기므로 1로 초기화된 것 그대로 내버려두었다.

 

DP2도 마찬가지 원리로 풀었으며, 맞았습니다를 받았다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 2491번 수열
# DP
import sys
input = sys.stdin.readline

N = int(input())
num_li = list(map(int, input().rstrip().split()))

dp1 = [1 for _ in range(N)] # 가장 긴 감소하는 수열
dp2 = [1 for _ in range(N)] # 가장 긴 증가하는 수열
for i in range(1, N):
    if num_li[i-1] >= num_li[i]:
        dp1[i] = dp1[i-1] + 1
    if num_li[i-1] <= num_li[i]:
        dp2[i] = dp2[i-1] + 1

print(max(max(dp1), max(dp2)))