백준 15897 (UCPC 2018 예선 H번) 잘못 구현한 에라토스테네스의 체

이 문제는 UCPC 때는 3시간 내내 붙잡고 있다가 못 푼 문제인데... 결국 풀었다.
내가 푼 방법을 정리해 보고자 한다.

----------------------------------------------
1  int n;
2  cin >> n;
3  int* sieve = new int[n + 1];
4  for(int i = 1; i <= n; i++) {
5      for(int j = 1; j <= n; j += i) {
6          sieve[j] += 1;
7      }
8  }

----------------------------------------------

주어진 코드에서 6번째 줄이 입력으로 들어오는 n에 따라 몇 번 실행되는지를 구해야 하는 문제인데, 예를 들어 n이 4라고 하면
j = 1, 2, 3, 4
j = 1, 3
j = 1, 4
j = 4
이렇게 총 9번 실행된다.

바깥쪽 for문의 i 값에 따라 안쪽 for문의 실행횟수가 결정된다고 볼 수 있다.
안쪽 for문에서 j = 1부터 시작하여 i만큼 더하면 n이하일 때까지 반복하므로,
각 i마다 (n - 1) / i 만큼 안쪽 for문이 실행된다.

근데 n이 최대 10억까지 입력으로 들어오기 때문에... 일일이 다 더했다간 시간초과이다.
여러 방법을 고민해보다가 n / 2, n / 4정도까지 줄이기도 해봤었는데... 역시나 1초에 들어오기는 버겁다.

하지만 잘 생각해보면 O(루트n)만큼으로 줄일 수 있다.
내가 찾은 방법을 설명하기가 쉽지 않아서, 예를 들어서 설명해 보겠다.

n이 12인 경우를 예로 들어보면,
j = 1부터 시작하고, n번 모두 1부터 시작하므로 n번 도는 것은 무조건 확정이고,
거기에 (n - 1)을 i로 나눈 몫을 구해서 더해야 한다. 그런데, 모든 i에 대해 그 몫을 구할 필요가 없다.
숫자(a) 자신과 1만 약수로 갖는 소수를 구할 때에도 보면, 2부터 (a - 1)까지 다 나눠보고 나누어 떨어지는지(1과 자기 자신 외의 약수가 있는지)를 알아보는 방법도 있지만, 굳이 다 나누어 볼 필요 없이 (루트a) 까지만 나누어 보면된다.
12를 예로 들면
2 * 6 = 12
3 * 4 = 12
4 * 3 = 12
6 * 2 = 12
에서 볼 수 있듯이, 2, 3까지만 나누어 보면 4, 6으로 다 나누어 본 것과 같으므로...
(루트a)이하의 수로 나누면 (루트a)이상의 수로 나눠본 것과 같다는 것을 알 수 있다.

마찬가지로 이 문제에서도 똑같이는 아니지만 비슷한 개념을 적용해 볼 수 있다.
n = 12라고 하면, 먼저 1부터 시작하므로 변수 ans(답)에 12를 저장해둔다.
그리고 (n - 1)인 11을 1부터 11까지 나눈 몫을 다 더해주면 답이 되는데,

1 * 11
2 * 5
3 * 3
4 * 2
5 * 2
6 * 1
7 * 1
8 * 1
9 * 1
10 * 1
11 * 1

가 된다. 그래서 12 + 11 + 5 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 = 41 이 답이다.

잘 보면 1 * 11 과 11 * 1, 2 * 5와 5 * 2, 가 짝을 이루고 있는 것을 볼 수 있는데,
x * x <= 11인 x = 3까지만 보면, 즉 1 * 11과 2 * 5를 보면 11 * 1과 5 * 2까지 해보지 않고
알 수 있다.

하지만, 좀 부족하다. 3 * 3은 당연히 짝이 없다해도, 4 * 2, 6 * 1, 7 * 1, ... 10 * 1 은 어떻게 예상할 수 있을까?
(루트n)까지 하는 것으로는 부족한 것이 아닐까? 다 해봐야 하지 않을까?

2 * 5로 5 * 2를 알 수 있다. 그런데  4 * 2를 알 수 있는 2 * 4는 왜 없을까? 4 * 2는 되는데 왜 2 * 4는 되지 않을까?

11 = 4 * 2 + 3 이지만 11 = 2 * 5 + 1이다. 즉 나누는 수가 2이냐 4이냐의 차이이다.
2로 나누면 나머지가 2보다 작아야 하기 때문에 몫이 크게 나온다. 4로 나누면 나머지가 4보다 작으면 되니까 몫이 2까지 나온다.

그럼 3 * 2는 어떨까? 3 * 2 + 5 = 11인데, 나머지 5가 3보다 크기 때문에 안된다.
4 * 2 + 3 = 11로 나머지 3이 4보다 작아서 가능한 것과 차이가 있다.

즉 2 * 5를 보면 5 * 2가 된다는 것은 바로 알 수 있지만, 4 * 2가 되는지, 3 * 2가 되는지는 판단하는 작업이 필요하다. 물론 이것을 일일이 확인하면 시간복잡도가 커진다.
위에서 보았듯이, x * 2가 가능하려면, n - x * 2 < x 가 되어야 한다.

여기서는 2이지만 이를 모든 경우에 적용하면
n - x * i < x 이어야 하고, 이를 정리하면, x > n / (i + 1) 이다.
즉, x * i가 가능한 x값의 하한값은 (n + i + 1) / (i + 1)이 되는 것이다.

lo = (n + i + 1) / (i + 1) 이라고 하면
lo값부터 (n - 1) / i 값까지 모두

lo * i
(lo + 1) * i
.
.
.
((n - 1) / i) * i

라는 것을 유추할 수 있는 것이니, ans += ((n - 1) / i - lo + 1) * i 를 해주면 된다.

단, 주의해야할 것은 3 * 3 같이 제곱 수들은 여러번 더해지면 안되는데, 한 번 더 더해진다.
그래서 (n - 1) / i 와 i값이 같을 때는 i만큼 빼줘야 한다.

자료형도 long long으로 하였고, 결국 이렇게 해서 AC를 받았다.