11053번: 가장 긴 증가하는 부분 수열

🔗 문제 ∙ 11053번: 가장 긴 증가하는 부분 수열

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 {10, 20, 30, 50} 이고 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N(1 <= N <= 1000)이 주어진다.
둘째 줄에 수열 A를 이루고 있는 Ai가 주어진다. (1 <= Ai <= 1000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

🔑 풀이

가장 '긴','증가하는' 부분 수열의 길이를 찾아야 한다.

• '증가하는' 이라는 말에서 수열을 왼쪽에서 오른쪽 으로 순회해야한다는 것을 알 수 있다.
  dp[i] 에는 i번째 원소를 마지막으로 하는 LIS의 길이를 저장한다.
  0 <= j < i 인 j번째 단계에서 가장 긴 LIS를 가지고 있는 단계와 합친다.

{10}, {20}, {10}, {30}, {20}, {50} 의 부분 수열들이 있을 수 있고, 포함하고 있는 값이 최대인 LIS를 만들어 나간다.

💁‍♀️ i = 0 ( 단계 )

• {10}
• dp[0] = 1

이전 단계 즉 합칠 부분 집합이 없으므로 다음 단계로 넘어간다.

# 현 단계 상황
dp = [1,1,1,1,1,1]
실제 의미 = [{10}, {10}, {30}, {10}, {20}, {50}]

---

💁‍♀️ i = 1 ( 단계 )

• {20}

집합의 최대 값이 20이고, 이전 단계 중 합칠 수 있는 집합은 합쳐야 한다.

• 이전 단계 후보( j ) : 0 단계
• A[0] < A[1]
• 10 < 20 이므로 합칠 수 있음

합친 결과물은 {10, 20} 로, 1단계에서의 LIS 이다.

# 현 단계 상황 
dp = [1,2,1,1,1,1]
실제 의미 = [{10}, {10,20}, {30}, {10}, {20}, {50}]

---

💁‍♀️ i = 2 ( 단계 )

• {30}
• 최대 길이의 증가하는 부분 수열을 만들기 위해서 이전 단계에서 합칠 수 있는 부분 집합 후보( j ) : 0, 1 단계
  - j = 0 {10} - A[0] < A[2]
  - 10 < 30
  - 결과 : {10, 30}
  • j = 1 {10, 20}
    • A[1] < A[2]
      • 20 < 30
      • {10, 20, 30} or {10, 30}
      • 결과 : {10, 20, 30}

즉, 이전 단계에서 합칠 수 있는 후보들을 모두 다 고려하여 차례로 LIS를 만들어 나간다.

# 현 단계 상황 
dp = [1,2,3,1,1,1]
실제 의미 = [{10}, {10,20}, {10, 20, 30}, {10}, {20}, {50}]

# 그 후, 3 단계는 
dp = [1,2,3,1,1,1]
실제 의미 =[{10}, {10,20}, {10, 20, 30}, {10}, {20}, {50}]

# 4 단계는 
dp = [1,2,3,1,2,1]
실제 의미 =[{10}, {10,20}, {10, 20, 30}, {10}, {10, 20}, {50}]

# 5 단계는 
dp = [1,2,3,1,2,4]
실제 의미 =[{10}, {10,20}, {10, 20, 30}, {10}, {10, 20}, {10,20, 30, 50}]

코드

n = int(input())
a = list(map(int, input().split()))
dp = [1]*n

for i in range(1, n):
    for j in range(0, i):
        if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp))

🛎 패스트 캠퍼스: 알고리즘/ 자료구조 온라인 강의의 해설을 참고하였음.

• 머리로 이해하는 거랑, 설명을 위해 풀어 쓰는 것은 전혀 다르다. 풀어서 쓰니 문제가 더 어려운거 같음 😂