[S2] 백준 11568 - 민균이의 계략 (Python3)

https://www.acmicpc.net/problem/11568

 

---

해결방법

최장 증가 부분 수열(LIS, Longest Increasing Subsequence)의 기초 문제이다. 이전에 이 시리즈를 풀어본 경험이 있어서 풀이의 틀은 쉽게 잡았다.

나는 시간복잡도가 O(n^2) 인 알고리즘으로 문제를 풀었다.

arr의 길이가 최대 1,000 이므로 O(n^2)은 1,000,000이라 제한시간(1초) 안에 충분히 통과가 가능하다.

더 빠른 방법은 O(n log n) 있다. n=1000 일때, n log n = 3000 이므로 더 빠르게 통과할 것이다.

풀이

이 문제의 풀이는 arr에 있는 각 원소를 주목해야 한다.

arr에 있는 원소들을 반복문으로 앞에서부터 차례차례 접근할 것이다.

이때 그 원소가 이 부분 수열의 가장 마지막 원소일때를 떠올려보아야 한다. 그리고 동시에 가장 긴 부분수열을 고민해야 한다.

---

코드

N = int(input())
arr = list(map(int, input().split()))

D = [1] * len(arr)

for i in range(N):
    for j in range(i):
        if arr[i] > arr[j]:
            D[i] = max(D[i], D[j]+1)

print(max(D))

코드 설명

원소(=arr[i], elem) 하나를 잡고 '이 원소가 부분 수열의 마지막 원소일 때 LIS는 몇일까?' 하는 질문을 계속 던지며 짰다.

그 원소 직전까지 for문을 돌리면서 elem보다 큰 원소를 찾으면 D[i]와 D[j]+1을 비교해서 더 큰 값을 D[i]에 저장한다.

동작 과정은 아래에서 조금 더 자세히 설명하겠다.

---

예제 1 입력으로 설명해보겠다.

5
8 9 1 2 10

입력이 위와 같으니 arr는 [8, 9, 1, 2, 10] 일 것이다.

for문으로 앞에서부터 차례대로 접근한다 했으니 일단 8먼저 보자.

• 8이 부분 수열의 마지막 원소일 때, 8(index:0) 이전에 존재하는 원소들(없음)로 이룰 수 있는 최장 증가 부분 수열은 '8' 뿐이므로 D[0] = 1이 된다.

 

다음은 9(index:1)를 보자.

• 9가 부분 수열의 마지막 원소일 때, 9(index:1) 이전에 존재하는 원소들(8)로 이룰 수 있는 최장 증가 부분 수열은 '8-9' 또는 '9'일 것이므로 D[1] = 2가 된다.

 

다음은 1(index:2)를 보자.

• 1이 부분 수열의 마지막 원소일 때, 1(index:2) 이전에 존재하는 원소들(8, 9)로 이룰 수 있는 최장 증가 부분 수열은 '1' 뿐이므로 D[2] = 1이 된다.

 

다음은 2(index:3)을 보자.

• 2가 부분 수열의 마지막 원소일 때, 2(index:3) 이전에 존재하는 원소들(8, 9, 1)로 이룰 수 있는 최장 증가 부분 수열은 '1-2'  또는 '2' 이므로 D[3] = 2가 된다.

 

마지막으로 10(index:4)를 보자.

• 10이 부분 수열의 마지막 원소일 때, 10(index:4) 이전에 존재하는 원소들(8, 9, 1, 2)로 이룰 수 있는 최장 증가 부분 수열은 '8-10', '8-9-10', '9-10', '1-10', 2-10', '1-2-10' 이므로 가장 긴 길이가 3이므로 D[4] = 3이 된다.

 

그러면 D는 [1, 2, 1, 2, 3]이고, max(D)=3 이므로 정답은 3이다.

---