(백준 알고리즘 문제풀이) 14003번 가장 긴 증가하는 부분 수열 5

문제

 

문제 링크

 

문제 접근

• 이분 탐색과 dp를 이용하여 문제를 풀어야 한다.
• 이분 탐색은 bi_sects를 구현하는 것을 이용한다.
• dp를 tuple을 통하여 value와 idx로 넣어서 이용한다.
• start가  dp의 길이보다 작을 경우에 dp의 이전 idx값을 temp에 추가한다. (이전 idx를 추적하기 위함)

코드

시간 초과 코드

import sys

N = int(sys.stdin.readline())
seq = list(map(int, sys.stdin.readline().split()))

dp = [[-1000000001] for _ in range(N)]
count = 0
for i in range(N):
    start = 0
    end = len(dp[count]) - 1
    while start <= end:
        mid = (start + end) // 2
        if dp[count][mid] < seq[i]:
            start = mid + 1
        else:
            end = mid - 1

    if start >= len(dp[count]):
        for k in range(count+1):
            if dp[k][len(dp[k])-1] < seq[i]:
                dp[k].append(seq[i])
    else:
        count += 1
        dp[count].append(seq[i])

dp.sort(key=lambda x: len(x), reverse=True)
result = ""
for i in range(1, len(dp[0])):
    result += str(dp[0][i]) + " "

# print(dp)
print(len(dp[0])-1)
print(result.strip())

통과 코드

import sys

N = int(sys.stdin.readline())
seq = list(map(int, sys.stdin.readline().split()))

dp = [(-1000000001, -1)]
temp = [0] * N

for i in range(N):
    start = 0
    end = len(dp) - 1
    while start <= end:
        mid = (start + end) // 2
        if dp[mid][0] < seq[i]:
            start = mid + 1
        else:
            end = mid - 1

    if start >= len(dp):
        temp[i] = dp[start-1][1]
        dp.append((seq[i], i))
    else:
        dp[start] = (seq[i], i)
        temp[i] = dp[start-1][1]


# print("DP", dp)
# print("TEMP", temp)
print(len(dp)-1)

result = list()
idx = dp[len(dp)-1][1]
while idx != -1:
    result.append(seq[idx])
    idx = temp[idx]

# print(result)
for i in range(len(result)-1, -1, -1):
    print(result[i], end=" ")

느낀점

시간 초과가 떳을 때, 정말 멘붕이었다.. 내 생각에는 for문을 한번 더 사용해서 시간 복잡도가 O(NlogN x N)이 되었기에 시간 초과가 일어난 것 같다. N의 값이 높기 때문에 시간복잡도도 신경써야하고, 인덱스 값을 추적도 해야하고 정말 어려웠다. 역시 플레티넘 문제인가. 그래도 처음으로 플레티넘 문제를 풀었다는 것에 뿌듯함을 느낀다.