cg456456   10달 전

음 전의 대답을 바탕으로 탐욕법 대신 windows 기법으로 해서 수정 했는데 시간 초과가 뜨네요 혹시 어디서 뜨는지 알수 있는지 가르쳐주시면 감사하겟습니다

adh0463   10달 전

짜신 소스로 봤을 때, 최악의 경우 N=1000000, K = 1일 때 시간 초과가 나네요.

현재 단계에서 가지고 있는 window에서 다음 단계로 넘어갈 때, 다음 단계에서 불필요한 부분만을 제거하고, 다음 단계에서 window에 포함되는 부분을 추가하는 방식입니다. 님이 짜신 소스는 for문을 하나 더 씀으로써 '현재 단계에 있는 window'를 재활용하지 못하고 있네요

요약하면 이중 for문이 문젭니다.

cg456456   10달 전

감사합니다 한번 for 문 안쓰고 최솟값 찾는 경우를 생각해야 될거 같군요

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