[백준알고리즘] 11722번: 가장 긴 감소하는 부분 수열 -Python

[백준알고리즘] 11722번: 가장 긴 감소하는 부분 수열 -Python

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

11722번: 가장 긴 감소하는 부분 수열

가장 긴 증가하는 부분 수열만 하더라도 정답 비율이 낮은 편은 아니더라도 유사한 문제를 계속 출제해서 그런 건지 정답 비율이 매우 높다. 이 문제도 마찬가지로 풀면 된다.

 

거의 풀었던 방식과 비슷하게 풀었다. 똑같이 max를 이용하고 slicing을 이용했다. 다만 이전과 바뀐 것은 이전 문제들의 경우 슬라이싱을 arr[:seq]으로 했다면 arr[seq+1:]의 형태로 현재 원소보다 큰 값들을 참조했다는 것이다. 그러다 보니 seq에 +1을 해주기 때문에 크기를 1000을 주어 인덱스를 0~1000까지만 갖도록 할 경우에 입력 원소로 1000이 들어갈 경우 1001을 인덱싱하며 오버플로우가 발생하게 된다. 따라서 초기 리스트의 크기를 1002로 잡았다.

 

import sys

N = int(sys.stdin.readline())
arr = [0] * 1002
sequence = list(map(int, sys.stdin.readline().split()))

for seq in sequence:
    arr[seq] = max(arr[seq+1:]) + 1

sys.stdout.write(str(max(arr)))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다