[Python] 백준/BOJ 15966번: 군계일학 (Silver 1)

💻 Problem

문제 보러 가기

 

효빈이는 어떤 수열에서 군계일학 수열을 뽑아내고자 한다. 단, 뽑은 항의 순서는 기존 수열에서의 순서를 유지해야 한다. 군계일학 수열은 각 항이 서로 연속적인 수열을 의미한다. 정확한 정의는 다음과 같다.

수열 중에 어떤 임의의 항 i에 대해서, ai=a1+(i-1)을 만족해야 한다.

길이가 N이고 정수로 이루어진 수열이 주어진다. 효빈이는 가장 긴 군계일학 수열을 가져가서 김승호 선생님께 자랑하려고 한다. 효빈이가 뽑아낼 수 있는 가장 긴 군계일학 수열의 크기를 출력하라.

 

💡 Approach

문제에서 a[i] = a[1] + (i - 1)를 만족해야 한다고 나와있다.

이 식은 등차가 1인 등차수열이다.

즉, a[i] = a[i - 1] + 1을 만족하면 된다.

 

해당 문제의 시간제한이 2초이므로 O(N^2)은 시간 초과가 나게 된다.

따라서 O(N)으로 풀 수 있는 DP를 활용한다.

 

✏️ Solution

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))
length = [1] * N

for i in range(N - 1):
    cnt = 1
    for j in range(i + 1, N):
        if arr[i] + cnt == arr[j]:
            cnt += 1
            length[j] = max(length[j], cnt)

print(max(length))

35점 코드이다.

시간복잡도가 O(N^2)이므로 서브태스크 3을 통과할 수 없다.

 

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))
dp = [0] * (10 ** 6 + 1)

for i in arr:
    dp[i] = max(dp[i], dp[i - 1] + 1)

print(max(dp))

a[i]의 최댓값이 10^6이므로 dp 배열을 10^6+1만큼 초기화했다.

N의 최댓값이 10^5이므로 시간복잡도 또한 10^5이다.