joonas   2년 전

솔루션이 아래 첨부한 코드의 구조였는데, 중간에 3*i >= j*j 가 없으면  $O(\sum_{j=1}^h (\sum_{i=1}^w (i+j))$ 정도로, 

else 문에 있는 for k=1 to i-1 때문에 오래걸릴거라 생각했습니다. (대충 O(W^2H) (W>H일때))

근데 W 범위가 10,000 이고, H의 범위가 100 밖에 되지 않아서, 중간에 3*i >= j*j 를 넣는다고 해서 시간복잡도가 얼마나 줄어드는 지 의문입니다.

아래 코드는 200ms 정도로 통과했는데, 최악의 경우라면 시간초과가 맞지 않나요?

저는 예제 입력으로 9999 99 를 넣으면 한 10초 뒤에 정답이 찍히네요.

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