띠용. 시간초과가 안나는게 이상한데요..ㄷㄷ
1158번 - 요세푸스 문제
자세히 설명해주실 수 있나요??
메모리문제라면 이해가 가는데 시간복잡도하고는 무슨 관계가 있는지 이해가 잘 가지 않습니다ㅠ
입력값이 크지 않아서 시간초과는 안날것 같다 판단했습니다.
근데 제가 질문드린것은 이해가 아직 안갑니다.
int 형을 사용했을경우 시간초과가 나지 않는데 long int를 사용한것은 왜 시간초과가 날까요?
32bit 데이터의 덧셈/곱셈/나눗셈 에 드는 시간과
64bit 데이터의 덧셈/곱셈/나눗셈 에 드는 시간을 비교해보면
당연히 64bit 데이터에 대한 연산시간이 더 크겠죠.
특히나 나눗셈(/)과 나머지(%)연산의 경우 다른 연산자보다 더더욱 많은 계산시간을 요구하기로 유명한 연산자입니다.
아무리그래도 수행시간이 2배씩이나 차이가 나지 않는 것이 보통이지만,
point%N 때문에 int형에 비해 long int가 2배의 시간을 잡아먹은 것으로 보입니다.
if(Arr[point%N]==0)
이 연산은 한칸 움직일 때마다 항상 호출되는 구문니까요..
어렴풋이 생각하던건데 정리가 안되고 있었습니다.
정확히 정리해주셔서 감사합니다.
댓글을 작성하려면 로그인해야 합니다.
junyoung292 7년 전
위에 큐 문제와 크게 다른것은 없지만
한가지 질문이 있어서 올립니다
아래 코드를 보시면 int point를 선언하여 원형큐를 사용하여 풀었습니다.
근데 여기서 원형큐의 위치를 나타내는 point를 int 형이 아닌 long int 로 선언하였을경우
시간초과가 뜨는것을 확인하였습니다.
시간초과가 나는 이유를 도무지 모르겠어서 질문드립니다.