14882번 - 다항식과 쿼리
차라리 오답이면 좋을텐데 시간초과나는 원인을 도저히 모르겟네요ㅠㅠ
python으로 짜서 시간초과 나오길래 cpp로도 짜봤는데 안되서 질문드립니다.
입출력문제인가 해서 ios::sync_with_stdio(false) 써보고, scanf나 printf로도 바꿔봤는데,
여전히 시간초과가 나는데 원인이 무엇일까요?
최대 int 동적할당 250000개니까, 대략 1mb정도는 문제 없는거 같고,
시간복잡도도 따로 내장함수 쓴게 없어서 O(NK) N<250000, K<250000이라서 그렇게 크지 않은거 같고,
로직은 그이상 최적화가 힘들어보이는데 무엇이 잘못된걸까요?
고수분들 도와주세요!!
시간복잡도를 구하는 이유는 시간초과가 나는지 검사하기 위해서입니다. 보통 계산식을 포함하는 for문 1억 번을 1초라고 생각하는데요, O(NK)이고 N,K<=250000이면 곱이 백억을 넘어가므로 실행 시간이 적어도 분 단위로 걸립니다.
그리고 이 문제는 시간 최적화를 통해 매우 어려운 분할정복 알고리즘인 FFT를 사용해야 하므로 다른 문제부터 풀어보시는 것을 추천합니다.
댓글을 작성하려면 로그인해야 합니다.
edgar 6년 전
차라리 오답이면 좋을텐데 시간초과나는 원인을 도저히 모르겟네요ㅠㅠ
python으로 짜서 시간초과 나오길래 cpp로도 짜봤는데 안되서 질문드립니다.
입출력문제인가 해서 ios::sync_with_stdio(false) 써보고, scanf나 printf로도 바꿔봤는데,
여전히 시간초과가 나는데 원인이 무엇일까요?
최대 int 동적할당 250000개니까, 대략 1mb정도는 문제 없는거 같고,
시간복잡도도 따로 내장함수 쓴게 없어서 O(NK) N<250000, K<250000이라서 그렇게 크지 않은거 같고,
로직은 그이상 최적화가 힘들어보이는데 무엇이 잘못된걸까요?
고수분들 도와주세요!!