문제에 적힌 N의 범위는 어떤 알고리즘을 쓰라는 힌트다. 1초에 대략 1억 번 연산한다는 눈금을 놓고 역산하면 N을 보는 순간 후보가 몇 개로 좁혀진다. 풀이가 안 떠오를 때 먼저 볼 곳이기도 하다.
N 범위별 허용 복잡도
N ≤ 10~11 O(N!)
N ≤ 24~25 O(2ᴺ)
N ≤ 300~500 O(N³)
N ≤ 5,000~10,000 O(N²)
N ≤ 50,000~100,000 O(N√N)
N ≤ 100,000~1,000,000 O(N log N)
N ≤ 10,000,000 O(N)
N이 개수가 아니라 범위로 주어질 때 O(√N), O(log N), O(1)
N이 20 이하면 2ᴺ이 허용된다. 부분집합을 전부 만들어봐도 100만 정도라 완전 탐색으로 밀어붙일 수 있다. 괜히 똑똑한 방법을 찾으려다 시간을 버릴 필요가 없다.
N이 100,000인데 O(N²)을 짰다면 100억 번이라 무조건 시간 초과다. 정렬을 끼워 O(N log N)으로 내리거나 이중 반복을 해시 테이블로 바꿔 O(N)으로 내려야 한다.
마지막 줄이 중요하다. N이 데이터 개수가 아니라 1 ≤ N ≤ 10억 같은 값의 범위로 주어지면 N을 다 훑는 것 자체가 불가능하다는 신호다. 수학적 성질을 찾거나 이분 탐색을 쓰라는 뜻이다.
주기를 찾아 반복 없애기
반복문을 썼다고 해서 늘 O(N)인 것은 아니다. 격자 안에서 개미가 움직이는 백준 10158번이 그런 예다. 격자는 2 ≤ W, H ≤ 40,000인데 시간 T가 2억까지 올라가서, T번 반복하면 시간 초과다.
움직임을 관찰하면 주기가 보인다. 시작 위치가 (2, ?)이고 W가 6이라면 2에서 6까지 4, 6에서 0까지 6, 0에서 2까지 2를 움직여 12만에 위치와 방향이 함께 처음으로 돌아온다. 주기가 2W인 것이다.
주기가 있다는 것은 나머지 연산으로 접을 수 있다는 뜻이다. 위치 대신 시간으로 보고 (x + t) % (2 * W)를 구한 다음, 그 값이 W를 넘으면 되꺾인 것이니 2W - x로 바꾼다. 반복문이 아예 사라지고 O(1)이 된다.
int currentX = (t + x) % (2 * w);
if (currentX > w) currentX = 2 * w - currentX;N의 범위가 터무니없이 클 때는 대개 이런 종류의 성질을 찾으라는 문제다.