[파이썬/python] 백준 15966 - 군계일학

문제

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

---

문제 설명

1. 군계일학 수열은 각 항이 연속적인 수열을 의미한다.
   1. 군계일학 수열은 어떤 임의의 $i$에대해서 $a_i = a_1 +(i-1)$을 만족해야한다.  
2. 길이가 N이고 정수로 이루어진 수열이 주어진다.
3. 뽑은 항의 순서를 유지하며 만들 수 있는 가장 긴 군계일학 수열의 크기를 출력한다.

---

풀이

길이가 $N$인 수열이 주어지는데 $N$의 범위는 $1$  $\leq$ $N$  $\leq$ $10^5$이다.

군계일학 수열의 정의 조건인 $a_i = a_1 +(i-1)$를 만족시키는 항을 모두 찾기 위해서는 약 $N^2$만큼의 연산이 필요하지만 문제의 시간 제한인 2초의 시간 복잡도는 약$O(2 *10^8)$이므로 $O(N^2)$은 $O(10^{10})$으로 시간 초과가 날 것이다. 따라서 O(N)의 시간복잡도를 가지는 DP를 사용하여 이전의 정보를 사용하여 탐색했다.   

 

1. 군계일학 수열은 $a_1$의 크기에서 숫자가 1씩 증가하는 수열이다. 따라서 현재 숫자까지의 군계일학 수열 크기는 이전 숫자의 군계일학 수열 크기 +1이다.
2. 수열을 순회하면서 (num의 군계일학 수열 크기, [num-1]의 군계일학 수열 크기  +1 )의 최댓값으로 갱신하면서 탐색하면 최대 길이를 구할 수 있다.
3. $a_i$의 크기만큼 DP배열을 선언한다.
4. 2에서 발견한 규칙을 통해 점화식을 세운다.
   1. 점화식 : dp[num] = max(dp[num], dp[num-1]+1

---

코드

import sys
input = sys.stdin.readline

N = int(input())
dp = [0 for _ in range(10**6+1)]
arr = [0]+list(map(int,input().split()))
for i in range(1,N+1):
    num = arr[i]
    dp[num] = max(dp[num], dp[num-1]+1)
print(max(dp))

---

시간복잡도

• 1차원 배열에서의 DP는 $O(N)$의 시간복잡도를 가진다.
• 최악일 때 $N = 10^5$ 이므로 약 $O(10^5)$의 시간복잡도를 가진다.