imno1234   2년 전

DDR 문제에서 계속 시간초과가 떠서 질문드립니다.

매 입력마다 두 발 중 한 발은 마지막으로 입력된 버튼을 밟아야한다는 점에 착안하여

d[i]=해당 n번째 턴에서 n번째 버튼을 밟은 발의 반대발 이 i번째 버튼에 머물러있을 때의 점수

로 두고 입력마다 d[i]를 갱신하였습니다. 시간 복잡도 O(n^2)에 메모리비용 적은 바텀업 방식 풀이라고, 좋다고 제출하였는데 계속 시간초과가 떠서 질문드립니다.

(물론, 제가 입력해본 예제 값들은 올바른 결과를 잘 보여주었습니다.)


제가 보는 책에서는 일반적으로 수 초에 10^8번 연산 가능하다고 보던데, 이 문제의 경우 O(n^2)풀이는 최대 100,000^2=10^10번의 연산~수백초 가 걸려서 시간초과가 뜨는것인지, 아니면 제가 잡아내지 못한 실수가 있는지 궁금합니다. 

djm03178   2년 전

요즘은 컴퓨터가 빨라져서 10억 정도까지는 됩니다. 하지만 100억은 여전히 너무 큽니다.

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