[백준2491] / 수열 - DP

 

백준2491

 

푼 날짜 : 2024.10.02

푼 문제 : [2491] / 수열

사용한 언어 : python

알고리즘 : DP

 

 

점화식 :

max_dp[i] = max_dp[i-1]+1 (if lst[i-1] <= lst[i])
min_dp[i] = min_dp[i-1]+1 (if lst[i-1] >= lst[i])

 

수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾아내어 그 길이를 출력해야 하므로 dp 배열을 2개로 나누었다.

 

조건은

i) 같거나 커지는 것

ii) 같거나 작아지는 것 

 

이므로

이전 값과 비교해서 연속적으로 이전 값과 같거나 커질 때, 이전 값과 같거나 작아질 때를 계산했다.

이후 각 배열의 max값을 찾아 더 큰 값을 출력하도록 구현했다.

 

 

코드 :

import sys

N = int(sys.stdin.readline())
lst = list(map(int, sys.stdin.readline().split()))

max_dp = [1 for _ in range(N)]
min_dp = [1 for _ in range(N)]

for i in range(1, N):
    if lst[i-1] <= lst[i]:
        max_dp[i] = max_dp[i-1]+1
    if lst[i-1] >= lst[i]:
        min_dp[i] = min_dp[i-1]+1
       
max_ = max(max_dp)
min_ = max(min_dp)
print(max(max_, min_))

 

 

할 일이 많은 관계로 오늘은 쉬운 문제로... 헤헤 ﾚ(Ⲻⲻ Ⲻ )ﾍ=͟͟͞͞