[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,리스트))) 기억해두자.
Author And Source
이 문제에 관하여([Python] 백준 2491_수열), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@soobin519/Python-백준-2491수열저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)