1074번 - Z
모든 점을 탐색하는 코드가 돌아갑니다.
https://www.acmicpc.net/source...
N = 2^(2n)이라 둘때
문제에서 요구하는 시간 복잡도는 사분면중 하나만 탐색해나가는 O(logN)풀이 인듯한데, 전수탐색하는 풀이 O(N)이 통과됩니다.
최악의 경우 2^30인데 이경우 대략 10억번의 연산정도 걸림니다.
1655번 문제(14https://www.acmicpc.net/proble...)와 마찬가지로
시간제한 2초가 널널하다고 생각됩니다. C++기준으로 0.1초로 줄여도 충분할듯하고 , 나머지 언어들에 대해서 보너스 시간을 0.6초 정도 주면 적절할 듯합니다.
질문 게시판을 확인해보면 O(N)풀이가 시간초과가 나는 경우가 있어서 요청드립니다.
한번 확인 부탁드림니다.
재채점했습니다.
댓글을 작성하려면 로그인해야 합니다.
tjdlfgns1234 5년 전
모든 점을 탐색하는 코드가 돌아갑니다.
https://www.acmicpc.net/source...
https://www.acmicpc.net/source...
N = 2^(2n)이라 둘때
문제에서 요구하는 시간 복잡도는 사분면중 하나만 탐색해나가는 O(logN)풀이 인듯한데, 전수탐색하는 풀이 O(N)이 통과됩니다.
최악의 경우 2^30인데 이경우 대략 10억번의 연산정도 걸림니다.
1655번 문제(14https://www.acmicpc.net/proble...)와 마찬가지로
시간제한 2초가 널널하다고 생각됩니다. C++기준으로 0.1초로 줄여도 충분할듯하고 , 나머지 언어들에 대해서 보너스 시간을 0.6초 정도 주면 적절할 듯합니다.
질문 게시판을 확인해보면 O(N)풀이가 시간초과가 나는 경우가 있어서 요청드립니다.
한번 확인 부탁드림니다.