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

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

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

11053번: 가장 긴 증가하는 부분 수열

부분 수열 중 증가수열로 가장 길게 만들 수 있는 길이를 구하는 문제이다. 이 문제를 해결하고 다른 사람들의 코드를 봤는데 나는 내 코드가 가장 간단한 것 같다.

 

우선 초기 리스트를 1~1000까지 잡아주기 위해서 1001만큼의 크기로 잡아준다. 수열을 이루고 있는 수가 1~1000이기 때문에 리스트의 해당 인덱스에 최대 길이를 저장할 것이다. 입력받은 수열에서 원소 하나씩 꺼내서 확인을 하는데 이때 해당 수보다 작은 원소들 중에서 가장 큰 길이에 +1을 시켜줄 것이다. 이렇게 할 수 있는 이유는 이전에 자신보다 작은 수가 나온 적이 있다면 그 수에 이어서 부분 증가수열을 만들 수 있기 때문인데, 자신이 추가됨에 따라 길이가 1 증가하기 때문이다.

 

그렇게 모든 입력값에 대해 처리를 하고 전체 리스트 중에서 가장 길었던 길이를 출력시키면 된다.

 

import sys

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

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

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

 

거의 대부분의 사람들은 N크기의 리스트를 준비하고 for문을 두 개 사용해서 입력값의 원소를 하나 선택하면 그 이전의 원소들과 비교하면서 현재의 길이를 측정했다. 나는 그 부분을 slice와 max를 이용해서 처리를 한 차이이다.

 

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