23631번 - 진심 좌우 반복뛰기
채점번호:35745421
전처리 O(N) 브루트포스가 통과됩니다.
시간 제한을 0.1초 이하로 수정해주세요.
T sqrt(N)은 통과하는게 의도이고 TN은 통과하지 않는게 의도라면, 데이터를 추가하는 방식으로도 해결할 수 있을 것 같습니다
채점번호의 코드를 보시면 데이터를 추가하는 방식으로는 실행 시간을 크게 늘릴 수 없을 것 같습니다.
코드를 봤는데 O(T+N)으로 동작하는 코드네요
제 테스트 케이스당 sqrt(N/K)에 동작하는 코드도 통과하는데 (35745686) 해당 코드들을 통과시킬지의 여부를 출제자분이 정해주시면 될 것 같습니다.
@kadrick
그리고 코드가 브루트포스라고 하기에는 음... 생각보다 이용해야 하는 관찰이 좀 있는 것 같습니다.
35745421번 코드의 입출력 방식을 scanf/printf에서 cin/cout으로 고쳤는데, 96ms에 동작하네요. 시간 제한을 0.1초로 줄이는 것으로는 해당 풀이를 막을 수 없어 보입니다. (제출: 35745711)
댓글을 작성하려면 로그인해야 합니다.
rhdqor213 2년 전
채점번호:35745421
전처리 O(N) 브루트포스가 통과됩니다.
시간 제한을 0.1초 이하로 수정해주세요.