글 읽기 - TLE 질문

sksms1375 2년 전 0

연속적인 부분 수열을 모두 구하면서(1개인 연속적인 부분 수열부터 N개인 연속적인 부분 수열 모두) LIS의 길이를 더해주고 답을 도출했는데 시간초과가 납니다

LIS는 O(nlgn)방식으로 풀어서 연속된 부분 수열을 구하기 위해 반복문으로 돌리면 n(n+1)//2번이기 때문에 O(n^2lgn)일거고 n=500이어도 충분히 시간초과가 안날거라 생각했는데... 어느부분을 줄여야할지 잘 모르겠네요

from bisect import bisect_left
import sys
input = sys.stdin.readline

array = []
for t in range(int(input())):
    n = int(input())
    for _ in range(n):
        array.append(int(input()))
    s = 0
    for i in range(1, n+1):
        for j in range(n):
            dp = [0]
            if i+j>n:
                break
            for k in range(j, j+i):
                if dp[-1] < array[k]:
                    dp.append(array[k])
                else:
                    dp[bisect_left(dp, array[k])] = array[k]
            s += len(dp)-1
    print("Case #"+str(t+1)+":", s)

rlatkdduq99 1년 전 0

혹시 어떻게 TLE 해결했을까요? 궁금합니다

sksms1375 1년 전 1

3중 for문 없이 2중 for문으로 lis를 판별하면 됩니다

예를 들어 [3, 2, 5, 6, 7] 이라는 배열이 있으면, [3]의 lis의 길이는 1, [3, 2]의 lis의 길이는 1, [3, 2 ,5]의 lis의 길이는 2, [3, 2, 5, 6]의 lis의 길이는 3, [3, 2, 5, 6, 7]의 lis의 길이는 4이므로 1+1+2+3+4 이렇게 보다

[3]의 lis는 [3]이고 길이는 1, 그 lis에 2를 넣으면 [3]이고 길이는 1, 5를 넣으면 [3, 5]이므로 길이는 2, 6을 넣으면 [3, 5, 6]이므로 길이는 3... 이므로 전과 동일합니다

rlatkdduq99 1년 전 0

감사합니다! 저도 3중 for문으로 해서 계속 안되었던 거 같네요!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

TLE 질문

sksms1375 2년 전 0

rlatkdduq99 1년 전 0

sksms1375 1년 전 1

rlatkdduq99 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말