📌 문제 요약

• 길이가 N인 수열이 주어진다.
• “증가하는 부분 수열(increasing subsequence)” 중
  가장 길이가 긴 것의 길이를 구하는 문제.
• 부분 수열이기 때문에 연속일 필요는 없다.
  └ 다만 순서는 유지해야 함.

---

🧠 내가 세운 접근 방식

처음엔 “수열을 앞에서부터 보면서, 각 위치에서 끝나는 LIS의 길이”를 저장하면 되지 않을까?
라고 생각했다.

이 문제는 “구간”이 아니라 “부분 수열”이기 때문에
어떤 수 seq[i]를 선택하려면,
그 이전의 원소 seq[j] (j < i) 중에서

seq[j] < seq[i]

이 조건을 만족하는 것들만 고려해야 한다.

그래서 DP 테이블을 다음처럼 정의했다.

dp[i] = i번째 원소를 ‘마지막 원소’로 갖는 LIS의 길이
LIS는 Longest Increasing Subsequence의 약자로, 가장 긴 증가하는 부분 수열을 의미한다.

이렇게 정의해두면 자연스럽게 점화식도 나온다.

---

🔍 점화식 형태

i번째 위치에서 고려할 선택지는 두 가지뿐이다:

1. 증가 조건을 만족하는 이전 인덱스 j를 골라,
   dp[j] + 1 로 이어붙이기
2. 이전에 자신보다 작은 값이 하나도 없다면
   → 자기 자신만 쓰는 길이 1

즉,

dp[i] = max(dp[j] + 1)   (단, j < i 이고 seq[j] < seq[i])
dp[i] = 1                (만약 조건을 만족하는 j가 없다면)

---

🧪 코드

아래 코드는 위 아이디어대로 구현한 O(N²) 정석 풀이다.

n = int(input())
seq = list(map(int, input().split()))
dp = [0] * n

dp[0] = 1

for i in range(1, n):
    candidates = []
    for j in range(i):
        if seq[i] > seq[j]:
            candidates.append(dp[j] + 1)
    
    if candidates:
        dp[i] = max(candidates)
    else:
        dp[i] = 1

print(max(dp))

---

⏱ 시간복잡도는? 괜찮을까?

이 코드의 시간복잡도는

바깥 for → N번
안쪽 for → 평균 N/2 정도
총 ≈ N²/2 → 대략 50만번 정도 (N = 1000일 때)

파이썬에서 50만 연산은 아주 가벼운 수준이라서
백준 기준 1초 안에 충분히 통과한다.

✔ 코딩 테스트에서 시간복잡도 감각을 잡는 팁

N 크기	안전한 시간복잡도 (Python 기준)
N ≤ 1,000	O(N²) OK
N ≈ 5,000	O(N²)는 경계, O(N log N) 추천
N ≈ 100,000	O(N log N) 또는 O(N)만 가능
N ≥ 1,000,000	사실상 O(N) 이하

→ 이 문제는 N ≤ 1000이므로 O(N²) 풀이가 정석.

---

🧭 배운 점 정리

• LIS 문제의 핵심은
  “i에서 끝나는 가장 긴 증가하는 부분 수열의 길이” 를 dp에 저장하는 것.
• 부분 수열이기 때문에
  연속 여부는 상관없고, 순서만 지키면 된다.
• “이전 값 중 현재 값보다 작은 것들만” 확인한다는 점이 중요하다.
• 시간복잡도 O(N²) DP는 N이 작을 때(1000 이하) 매우 효과적.
• 이후에 N이 더 큰 LIS 문제(예: 12015, N ≤ 100만)를 만나면
  이분 탐색을 이용한 O(N log N) 풀이가 필요해진다.