[백준] 2491.수열 (Python)

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

2491번: 수열

 

1️⃣ DP를 활용하는 문제

2️⃣ 증가할 때와 감소할 때를 나누어 배열을 만들어서 증가하는 상태에서는 증가배열에 더해주고, 감소하는 상태에서는 감소배열에 더해주었다.

3️⃣ 이전 값과 같은 상태에는 증가와 감소 양쪽 모두에 더해주었다.

 

n = int(input())
arr = list(map(int, input().split()))
isTrue = [1]*n
isFalse = [1]*n

for idx in range(1, n):
    if arr[idx] < arr[idx-1]: # 감소하면
        isFalse[idx] = isFalse[idx-1]+1
    elif arr[idx] > arr[idx-1]: # 증가하면
        isTrue[idx] = isTrue[idx-1]+1
    else: # 같으면
        isFalse[idx] = isFalse[idx - 1] + 1
        isTrue[idx] = isTrue[idx - 1] + 1

print(max(max(isTrue), max(isFalse)))

 

✏️메모

• 디피 너무 어렵다🥲
• 연습이 아주아주 많이 필요할 것 같다. 화이팅!