[PY] 11503 : 가장 긴 증가하는 부분 수열

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

DP는 잘 모르고, 이분 탐색이 활용 가능한 문제라고 하니 그런가보다 하고 풀었다.
다양한 상황에서 다사다난했다. 우선 바로 문제가 생겼던 것이 :

1. 한 아이템도 1개의 수열이라 볼 수 있으나 이것이 카운트 되지 않아 수동 처리가 필요했다.

2. 선택된 아이템 바로 다음이 아닌 더 많은 선택지를 고려 해야했다.

테스트케이스 ac 라는 사이트가 많은 도움이 되었다. 어쨌든 그렇게 완성한 코드가 있는데 시간 초과가 났다.

import sys

# 11053 여기에 잠들다 11시 34분
# 최선을 다해서 풀었지만 시간초과로 더 이상 수행 할 수가 없다.
fieldLength = int(sys.stdin.readline())
field = list(map(int, sys.stdin.readline().strip().split()))[:fieldLength]
memo = {}

def getMore(reqCount, lastIdx, selectedCnt):

    if(reqCount, lastIdx, selectedCnt) in memo:
        return memo[(reqCount, lastIdx, selectedCnt)]

    if reqCount == selectedCnt:
        return True
    
    for i in range(lastIdx + 1, fieldLength):
        if(field[i] > field[lastIdx]):
            if(reqCount - selectedCnt <= fieldLength - i):
                canContinue = getMore(reqCount, i, selectedCnt + 1)
                if canContinue: 
                    memo[(reqCount, lastIdx, selectedCnt)] = True
                    return True
            else:
                memo[(reqCount, lastIdx, selectedCnt)] = False
                return False

                
    memo[(reqCount, lastIdx, selectedCnt)] = False
    return False


def binarySearch(start, end):
    result = 0
    
    while start <= end:
        canNext = False

        mid = (start + end) // 2
        for i in range(fieldLength):
           if mid > fieldLength - i:
                break
           
           canNext = getMore(mid, i, 1)
           if(canNext):
                break
              
        if(canNext):
            result = max(result, mid)
            start = mid + 1
        else:
            end = mid - 1
        
    if(start > end):
            if(result == 0):
                return 1
            return result
    
print(binarySearch(0, fieldLength))

하루종일 매달린건데 시간 상 최적화를 더 수행 할 수가 없었다. 전 문제로 풀었던 공유기 관련 문제의 상황에서 탈피 해야 했다.

충격적 영감을 받으셨던 분이 알려주셨는데 영상 하나를 보니 소름이 돋더라 ..

https://youtu.be/on2hvxBXJH4?si=ZdQxC8Y-yLcc8Nax

너무 간단한 문제가 되어버렸다.

1. 우선 전체 데이터로써 주어진 배열의 첫번째 데이터를 새로운 배열에 넣는다.

2. 배열을 순회한다. 각각의 아이템이 주어지면 새로운 배열의 마지막과 비교한다.

• 새로운 배열의 마지막 위치보다 작으면 배열 안의 있는 값과 대체 될 수 있으니 그 안에서 값을 새로이 탐색한다.
• 그렇지 않으면 원소로 넣어서 길이를 늘릴 수 있게 된다.

말이 안돼.

import sys, bisect

fieldLength = int(sys.stdin.readline())
field = list(map(int, sys.stdin.readline().strip().split()))[:fieldLength]

def longestIncreasingSubsequence(arr, arrLength):
    tmp = []
    tmp.append(arr[0])
    theLength = 1
    for i in range(1, arrLength):
        if(arr[i] > tmp[theLength - 1]):
            tmp.append(arr[i])
            theLength += 1

        else:
            ind = bisect.bisect_left(tmp, arr[i])
            tmp[ind] = arr[i]
    return theLength


print(longestIncreasingSubsequence(field, fieldLength))