BOJ 11722

Input

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

import sys
input = sys.stdin.readline

n = int(input())
A = [1000]*1000
A[:n] = map(int, input().split())

DP

비슷한 문제를 풀어봤던 기억이 있어서, 그 방법대로 접근하려 했지만 문제를 풀어보니 내가 그 방식으로 풀고 있지 않았다.

원래는 체크하고 있는 값보다 큰 값의 index를 dp에 저장하고 n-1부터 시작해서 dp에 저장된 index를 연속적으로 방문하며 cnt+1 해나가는 방식을 썼던 것 같은데,

이번 문제는 index를 저장하는 것이 아닌, 체크하는 index 기준 긴 수열의 길이를 max로 비교하며 dp에 저장해나가고, 최종적으로 가장 큰 값을 출력하면 됐다.

예시를 풀어보면 다음과 같이 되는데,

"""
A   = [10, 30, 10, 20, 20, 10]
dp  = [ 1,  1,  2,  2,  2,  3]
"""

여기서 히든 케이스는 max 를 이용해 기존에 저장된 길이와 비교하여 큰 값으로 대체해야 한다는 점이다.

히든 케이스를 예시로 들어보면,

"""
A   = [10, 40, 30, 40, 10, 20, 20, 10]
dp  = [ 1,  1,  2,  1,  3,  3,  3,  4]
"""

푸는 방식을 일반화 해보니, 앞에서부터 체크해나가되 dp 값을 저장하기 위해서는 해당 index로부터 뒤로 가고 있더라. 코드로 짜보면 다음과 같다.

for a in range(1, n):
  for b in range(a-1, -1, -1):
    if A[b] > A[a]:
      dp[a] = max(dp[a], dp[b] + 1)

전 값과 비교하면서

• 전 값이 클 경우, 기존 dp[a] 에 저장된 길이와 dp[b] 를 비교해 max 값을 저장한다.
• 여기서 끝내지 않고 index=0까지 방문하기 때문에 최외곽 index 기준으로 가장 긴 수열의 길이를 저장하게 된다.

Output

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

print(max(dp))

IndexError로 인한 런타임 에러를 방지하기 위해 최대 길이의 배열을 생성했으므로… dp[n-1] 이 아닌 max 를 이용해 가장 큰 값에 접근해야 한다.