백준 11722번 - 가장 긴 감소하는 부분 수열 (LDS) 파이썬

📌 백준 11722번 - 가장 긴 감소하는 부분 수열 (LDS)

✨ 문제 요약

수열이 하나 주어졌을 때,
그 수열에서 감소하는 부분 수열 중 가장 긴 길이를 구하는 문제입니다.

---

🧠 문제 해석

• LIS(가장 긴 증가하는 부분 수열)와 반대 개념
• 즉, 수열의 요소들이 점점 작아지는 방향으로 이어져야 함
• 연속되지 않아도 되고, 순서만 지켜지면 됨

---

🔧 점화식 설계

dp[i] = i번째 원소를 마지막으로 하는 가장 긴 감소하는 부분 수열의 길이

for i in range(N):
    for j in range(i):
        if arr[i] < arr[j]:  # 감소 조건
            dp[i] = max(dp[i], dp[j] + 1)

---

🧱 DP 테이블 예시

입력: arr = [10, 30, 10, 20, 10]

i arr[i] dp[i] 의미 (i까지 고려했을 때 감소하는 수열 길이)

0	10	1 (처음 원소)
1	30	1 (증가하므로 새로 시작)
2	10	2 (30 → 10)
3	20	2 (30 → 20)
4	10	3 (30 → 20 → 10)

---

✅ 정답 코드 (Python)

N = int(input())
arr = list(map(int, input().split()))
dp = [1] * N  # 각 원소는 최소 자기 자신만으로 1개 수열

for i in range(1, N):
    for j in range(i):
        if arr[i] < arr[j]:  # 감소하는 조건
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

---

🧩 배운 점

• 가장 긴 감소하는 부분 수열(LDS)은 LIS와 거의 동일한 구조
• 핵심 차이는 조건: arr[i] > arr[j] 대신 arr[i] < arr[j]
• 완전탐색처럼 보이지만, DP로 이전 최적값(dp[j])을 누적하는 구조
• LIS는 O(N log N)으로도 가능하지만, 이 방식은 O(N²)로 충분

---

🎓 정리

항목 설명

문제 유형	DP (Longest Decreasing Subsequence)
점화식	dp[i] = max(dp[j] + 1) if arr[i] < arr[j]
초기값	dp[i] = 1 (자기 자신만 포함해도 길이 1)
시간복잡도	O(N²)

---

🏷 해시태그

#DP #LDS #백준11722
#가장긴감소하는부분수열 #동적계획법
#백준Python #알고리즘공부

```