백준 2491 : 수열 (Python)

본문 링크

N=int(input())

L=list(map(int,input().split()))
dp_up=[0]*(N+1) ; dp_down=[0]*(N+1)

for i in range(1,N):
    if L[i]>=L[i-1]:
        dp_up[i]=dp_up[i-1]+1
    if L[i]<=L[i-1]:
        dp_down[i]=dp_down[i-1]+1

print( max( max(dp_up) , max(dp_down))+1)

📌 어떻게 문제에 접근할 것인가?

가장 긴 증가하는 수열과 가장 긴 감소하는 수열값중 더 큰 값을 구하는 문제이다.

$dp$ 배열을 만들어 주고 0 으로 초기화 해준다.
만약 값이 증가하면 $dp$$up$ 배열에 이전값과 1 을 더한값을 넣어준다.
이전값이 0 보다 크면 연속해서 증가하고 있다는 의미이다.

반대로 $dp$$down$ 배열도 만들어 줘서 똑같이 해준다.

마지막으로 리스트 값중 가장 큰값을 출력한다.

✅ 코드에서 주의해야할 부분

• $dp$ 배열의 크기는 $N+1$로 잡는다.
• 값을 출력할때 처음에 1 개는 이미 선택한 상태이니 최대값에 1 을 더한 값을 출력한다.