static int table[100000 + 1];
static int ans[100000 + 1];
static int N;
static void table_init()
{
for (int i = 1; i <= 100000; i++)
{
//i의 배수 중 100000 이하인 것들에 대해서,
for (int j = 1; i * j <= 100000; j++)
table[i * j] += 1;
//for (int j = 1; j <= 100000 / i; j++)
//table[i * j] += 1;
}
int max = 0, number = 0;
for (int n = 1; n <= 100000; n++)
{
if (table[n] >= max) //n이 더 커지게 됨,
{
max = table[n];
number = n;
}
ans[n] = number;
}
}
static int solution(void)
{
scanf("%d", &N);
return ans[N];
}약수의 개수를 구하는 방법은 아래의 사이트에서 참조하였다.
https://mygumi.tistory.com/122
처음에 약수의 개수룰 구하기 위해서 소인수분해 하여 찾아보았다.
역시 타임아웃이 발생하였다.
다음에는 비트연산과 동적계획법을 사용해보았다.
비트연산을 이용하여 2의n승 꼴은 소인수분해하여 찾지 않아도 되고
12 같은 수는 2 와 6의 곱으로 이루어지므로, 이들을 이용하여 그 개수를 계산해내는 것이다.
물론 방법적으로 틀린 부분도 있으리라 생각했다. 그리고 테이블을 구축하는 시간도 너무 길었다.
그래서 구글링 해보니 어렵지 않게 그 방법을 찾을 수 있었다.
첫번째 for문은 시작할 값을 선택하는 것이고,
중첩된 for문은 그 값의 배수 중 100000이하의 값 까지만 반복하는 것이다.
그 다음 반복문은 N이하 중 약수의 개수가 가장 많은 수를 탐색하는 과정이다.
현재 n까지 가장 많은 약수의 개수와 그 값을 최신화하면서
ans 테이블을 초기화 하는 것이다.
특히 if절에서 >= 로 해야하는데,
그 이유는 n이 점점 커지므로 a < b 에서 a의 약수개수와 b 약수개수가 같더라도, b이하에서는 b가 약수의 개수가 가장 많으면서 제일 큰 값이기 때문이다.
