[Python] 백준 2491_수열

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

이 문제는 다이나믹 프로그래밍(DP)을 이용하여 해결할 수 있는 문제이다.

1.DP정의

• dp: i번째까지 왔을때 수열의 최대 길이
  이차원리스트로 하여 d[0]:증가할때/ d[1]:감소할때
• dp테이블은 처음에 모두 1로 세팅
  d= [[1]*n for _ in range(2)]
  

2. 점화식 찾기

증가하거나/ 감소할때
d[i] = d[i-1]+1

**여기서 중요한 조건은 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열을 구하는 것이다. 연속할때만 만족한다는 조건을 잘 기억하자.

3.코드

import sys
input  = sys.stdin.readline

n = int(input())
num = list(map(int,input().split()))

#dp: i번째까지 왔을때 수열의 최대 길이-증가할때/감소할때 
d = [[1]*n for _ in range(2)]

for i in range(1,n):
    if num[i-1]<=num[i]: #증가할경우
        d[0][i] = d[0][i-1]+1                         
    if num[i-1]>=num[i]: #감소할경우
        d[1][i] = d[1][i-1]+1
print(max(map(max,d)))

이차원 리스트의 최대값을 구하는 방법은 max(map(max,리스트))) 기억해두자.