1222번: 홍준 프로그래밍 대회

1222번: 홍준 프로그래밍 대회 - 수학

N개의 수가 주어질 때 이들 중 X로 나누어 떨어지는 수의 개수 * X의 값의 최대값을 출력하는 문제이다.

N은 최대 200,000이며 수의 최대값은 2,000,000으로 N^2으로 보는 방법은 당연히 시간 초과이다.

풀이는 이러하다. 2,000,000여개를 담을 수 있는 배열 A을 만든 뒤 이 배열에는 수들의 개수를 담는다.

그 다음 1 ~ 2,000,000를 보며 지금 보는 수를 X라 할 때 A[X], A[2*X], A[3*X] ... 의 값을 더한다면

X로 나누어 떨어지는 수의 개수가 된다.

이들 중 2이상인 수에 대해 X와 곱한 값이 가장 큰 값을 출력하면 풀 수 있는 문제이다.

이 때의 시간복잡도를 계산해보면 2,000,000개의 모든 수를 X가 1일 때는 2,000,000개를 보지만

2일 때는 절반인 1,000,000개, 3일 때는 666,666개 4일 때는 3일 때는 500,000개...로 줄어들으며

이는 2,000,000을 S라고 할 때 S/1 + S/2 + S/3 ... + S/S가 된다는 것을 알 수 있다.

이는 S(1/1 + 1/2 + 1/3 + ... 1/S)로 표현할 수 있으며 1/1 + 1/2 + 1/3 + ... 1/S는 조화급수의 합의 근사값인

대략 ln(S + 1)이다. 그러므로 이 알고리즘의 시간복잡도는 S * ln(S + 1)이 되는 것을 알 수 있다.

이는 시간 내에 풀 수 있으며 풀이 및 구현은 간단하지만 발상 및 시간복잡도에 관하여 생각을 하지 못한 문제였다.