글 읽기 - Lua에서 시간초과가 나는 문제가 있습니다.

mininii 1년 전 0

string.sub가 느리다고 생각되서 배열에 문자열 전처리 후 dp로 풀었는데도 시간초과라고 나오네요...

반례가 있는건지, 언어 자체 속도 문제인지, 알고리즘 문제인지 궁금합니다.

a=io.read()
b=io.read()
at={}
bt={}
t={}
for i = 1, #a do
	at[i]=string.sub(a, i, i)
end
for i = 1, #b do
	bt[i]=string.sub(b, i, i)
end
for i = 1, #a do
	t[i]={}
end
function LCS(x,y)
	if x<=0 or y<=0 then return 0
	else
		if t[x][y]==nil then
			if at[x]==bt[y] then
				t[x][y]=LCS(x-1,y-1)+1
			else
				if LCS(x-1,y)>LCS(x,y-1) then
					t[x][y]=LCS(x-1,y)
				else
					t[x][y]=LCS(x,y-1)
				end
			end
		end
		return t[x][y]
	end
end
print(LCS(#a,#b))

mininii 1년 전 0

해결했습니다.

극한의 최적화로 쥐어짜내니까 아슬아슬하게 94ms로 맞았습니다…ㅠㅠㅠ

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

문제

문제

출처

ICPC

Lua에서 시간초과가 나는 문제가 있습니다.

mininii 1년 전 0

mininii 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말