-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
duration 1초 문턱 판단
20.07.17 14:07 작성 조회수 163
0
영지선택문제말고도 small large문제들이 많은데, 그 1초 넘는지 안넘는지 대략적으로 어느정도로 생각하면될까요?
계산량이 대략 어느정도? 라고 생각하면 1초일지 궁금합니다.
it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
51. 영지 (territory) 선택 (large : 2차원 배열 구간합 : 제한시간 1초 : DP)
강의실 바로가기
답변을 작성해보세요.
0
김태원
지식공유자2020.07.18
문제마다 판단이 조금씩 다르고 채점하는 서버의 성능에 따라 차이가 있습니다. 같은 문제를 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;
}
답변 1