[백준 2024/03/27] 12015번 가장 긴 증가하는 부분 수열 2

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

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

 

1. 접근 방법

굉장히 익숙한 문제여서, 내가 이 문제를 제출을 안했었나? 하고 같은 방법으로 다시 풀고 제출했더니, 시간 초과가 되었다.

https://potatoscatteringsmile.tistory.com/206

[백준 2024/03/23] 11053번 가장 긴 증가하는 부분 수열

 

이 문제였다..ㅎㅎ

 

그래서 답을 보게 되었고 해석하고 다시 혼자서 코드를 작성하고 제출하게 되었다.

 

11053번 문제는 dp를 만든 후, 해당 dp까지 도달하는데의 최댓값들을 저장해 두었다. 

 

이번문제는 그러하지 않고, start와 end를 구성한 후, start와 end 값이 동일해진다면, 

tails[start] 에다 현재 위치의 값을 넣어주는 방식으로 진행하였다.

 

우선 tails = [0]*n 으로 만들어 주었다.

이후 중간 값을 구해주었다. (start + end) //2

 

만약 해당 값이 tails[m] 보다 크다면, 해당 값은 tails리스트에서 m 보다 위쪽에 위치해야 한다.

따라서 start를 m + 1로 올려주었다. 

 

만약 작다면, tails[m] 보다 낮은 index에 해당 값이 위치시키도록 해야하기 때문에, 

end 를 m 인덱스로 내려주었다.

 

이때, 나는 왜 start 는 m+1이고 end는 m인지 의문이 들었고, 생각해 보니, 만약 현재 tails 에 저장되어있는 값들보다 큰 값인 경우엔, 

맨뒤 + 1 인덱스에 저장해 주어야 함을 깨달았다.

 

만약 tails에 아래와 같이 저장이 되어 있다고 가정하자.

[10, 20, 0, 0, 0, 0 ] 라고 저장이 되어 있고 현재 15의 위치를 결정 짓고 있다.

15의 경우 20을 대치한 위치에 값이 들어가게 될 것이다.

 

즉, [10, 15, 0, 0, 0, 0 ] 으로 값이 저장되게 된다.

이렇게 저장하는 이유는 어짜피 10 -> 20 혹은 10 -> 15로 밖에 값이 진행이 안된다.

그럴 때에는 작은 값으로 대치시켜야, 추후 숫자들에 대해서 더 가능성이 있을 수 있기 때문이다.

즉, 이후 값으로 17이 나오게 된다면, 10 -> 15 -> 17로 진행이 가능하지만, 

만약 20을 남겨두게 된다면, 10 -> 20 -x-> 17이 되기 때문이다.

 

size의 경우 tails의 값이 채워지기 직전인 index를 가리키게 된다.

그래야지, end = size를 통해 tails의 끝 값이 가늠 가능하기 때문이다.

max(start +1, size)를 하는 이유는 현재 값이 저장된 인덱스에 + 1을 하는 것이고, size는 이전 tails의 크기를 나타낸다.

만약 맨 뒤에 값이 저장이 되었다면, 갱신이 될 것이고 그렇지 않다면 이전의 크기를 유지한 채로 다음 for 문으로 넘어가게 될 것이다.

 

2. 코드

def longest_length(nums, n):
    tails = [0] * n
    size = 0
    for i in nums:
        start = 0
        end = size

        while start != end:
            m = (start + end) // 2

            if tails[m] < i:
                start = m + 1
            else:
                end = m

        tails[start] = i
        size = max(start + 1, size)

    return size


n = int(input())
nums = list(map(int, input().split()))
print(longest_length(nums, n))