duration 1초 문턱 판단

Question

영지선택문제말고도 small large문제들이 많은데, 그 1초 넘는지 안넘는지 대략적으로 어느정도로 생각하면될까요?  계산량이 대략 어느정도? 라고 생각하면 1초일지 궁금합니다.

김태원 · Answer

문제마다 판단이 조금씩 다르고 채점하는 서버의 성능에 따라 차이가 있습니다. 같은 문제를 small, large로 한 것은 small형은 생각나는대로 코드구현해도 1초 통과가 되는 입력크기란 이야기고, large 형은 생각나느대로 코드구현하면 1초 통과가 안된다는 의미로 그렇게 만든것이니 참조하시기 바랍니다. 대략 1초의 계산량을 이야기하면 채점서버가 적당한 노트북 수준일 때 9번의 모두의 약수 문제를 아래와 같이 O(n^2) 알고리즘으로 짜면 입력크기 25000정도가 1초 정도 걸리는 것 같습니다. #include<bits/stdc++.h> using namespace std; int main(){ int n, cnt; scanf("%d", &n); for(int i=1; i<=n; i++){ cnt=0; for(int j=1; j<=i; j++){ if(i%j==0) cnt++; } printf("%d ", cnt); } return 0; }