🗨️ Comment
- 앞에서 부터 순회 / 뒤에서부터 순회 모두 가능 ! 하단 코드에 주석으로 표시
TestCase
6
10 30 10 20 20 10- 10 ⇒
[1, 1, 1, 1, 1, 1] - 30 ⇒
[1, 1, 2, 2, 2, 2] - 10 ⇒
[1, 1, 2, 2, 2, 2 ] - 20 ⇒
[1, 1, 2, 2, 2, 2] - 20 ⇒
[1, 1, 2, 2, 2, 3] - 맨 처음 10입장에서는 뒤에 자기보다 감소하는게 없다 → DP배열에 변화 X
- 30입장 → 10이든, 20이든 자신보다 작다
30일때 가장 감소하는 길이(현재는 1) + 1
→ 그런데 만약에 30 이전에, 50, 40이 있었다면[50-40-10] 으로 길이가 3일 수도 있음
→ 30입장에서는 이전의 값을 굳이 확인할 필요가 없도록, max로 최댓값을 확인하면서 갱신해야한다
⚠️ Error
- for문에서 인덱스 경계값 문제로 틀림
max처리 안해줘서 틀림
🥳 정답코드
'''
23.05.02
12:20 ~ 12:40
'''
# Error : 58% 에서 틀림 / 해결 -> for문 인덱스 경계값 문제
# 1초 / 256MBa
# N : 수열A의 크기 / 1이상, 1000이하
N = int(input())
_list = list(map(int, input().split()))
# Solution
# DP[i] : [i]까지 포함해서, 가장 길게 감소하는 수열의 갯수
# [i]까지 오면서 감소하기 -> [i]앞에, 더 큰값들이 있어야함
DP = [1] * (N)
# 앞에서부터
# i의 뒤에서 더 작은 값들 갱신해가기
for i in range(N-1):
for j in range(i+1, N):
if _list[i] > _list[j]:
DP[j] = max(DP[j], DP[i] + 1 )
# 뒤에서부터
# i의 앞에 더 큰 값들 갱신해가기
# for i in range(N-1, 0, -1):
# for j in range(i-1, -1, -1):
# if _list[j] > _list[i]:
# DP[j] = max(DP[j], DP[i] + 1)
# Output : 수열의 가장 "긴" 감소하는 부분 수열 구하기
print(max(DP))