8567. 약수의 개수가 많은 수

이 문제에 오버타임에 대한 댓글이 있어서 데이터량이 큰 것을 알았다.  또한. 이 문제의 경우에는 테스트 케이스 수에 대한 정보도 없어서 테스트 케이스가 얼마나 많이 들어올지도 모른다는 것이다. 

그래서 첫 번째로 생각한 솔류션은

list 배열에 각 인덱스에 대응하는 약수 개수를 저장해놓고 처음부터 각 값까지 max값을 계산해였다. 

하지만, 이 경우, 문제 자체의 개수도 많았기에 5개뿐이 맞추지 못했다. 

그래서 새로운 솔류션을 생각했다. 

list 배열에 차원을 하나 더 늘려 그 숫자까지의 max 값을 저장하는 것이었다. 

그렇게 되면 처음 약수의 개수를 찾는 for문과 그 숫자까지의 max 값을 찾는 for문을 이용하여 값을 빠르게 찾을 수 있다.

시간복잡도는 100000(약수 개수 찾기)+100000(max 값 찾기)+N(문제의 개수). 즉, 선형시간에 가능하다

 

#include<stdio.h>
int list[100001][2] = { 0 };
int main(void) {
	freopen("inp.inp", "r", stdin);
	freopen("out.out", "w", stdout);

	int k = 0;
	for (int i = 1; i < 100001; i++) {
		k = i;
		while (k < 100001)
		{
			list[k][0]++;
			k += i;
		}
	}
	int max = 0;
	int max_value = 0;
	for (int i = 1; i < 100001; i++) {
		if (max_value <= list[i][0]) {
			max = i;
			max_value = list[i][0];
		}
		list[i][1] = max;
	}
	int ts = 0;
	scanf("%d", &ts);
	int number = 0;
	for (int q = 0; q < ts; q++) {
		scanf("%d", &number);
		printf("#%d %d\n", q + 1, list[number][1]);
	}

	return 0;
}