백준[1241] 머리 톡톡

https://www.acmicpc.net/problem/1241

 

첫 아이디어는 각 학생들의 머리위 숫자에 배수를 한 지점에 1씩 더하는 아이디어다.

2 1 2 3 4를 예를 들면, 2는 2, 4에 1을 더하고 1은 1, 2, 3, 4, 3은 3, 4는 4 이렇게 하면 결과는 다음과 같다.

 

arr[1] = 1, arr[2] = 3, arr[3] = 1, arr[4] = 3

 

결론부터 말하지만 이 코드는 시간초과가 난다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
#include <map>
#include <set>
#include <string>
#define INF 987654321
#define lld long long
#define MAX_N 1000001

using namespace std;

int arr[MAX_N];

bool customCompare(const pair<int, int>& a, const pair<int, int>& b) {
	return a.second < b.second;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin >> n;
	vector<int> v(n);
	for(int i = 0; i < n; i++) {
		int x; cin >> x;
		v[i] = x;
	}
	for(int i = 0; i < n; i++) {
		int x = v[i];
		for(int j = 1; x*j < MAX_N; j++) {
			arr[x*j]++;
		}
	}

	for(int i = 0; i < n; i++) {
		cout << arr[v[i]]-1 << '\n';
	}

	return 0;
}

 

 

이 코드가 시간 초과가 나는 이유는 "배수"에 있다. 예를들어 초기 배열이 1로만 이루어져있다면, 1은 1부터 1,000,000까지 전부 순회해야한다. 이것을 최적화하려고 배열의 최대값인 max_val을 구하여 max_val까지만 순회하려 해도 만약 배열이 전부 1이고 하나만 1,000,000이라면 이 또한 전부 순회하는 경우가 생긴다.

역으로 생각하여 배수가 아닌 약수를 구해보는 것으로 풀어본다.

예를 들어 12의 약수는 1, 2, 3, 4, 6, 12이다. 두 수의 곱으로 보면 1*12, 2*6, 3*4 이렇게 표현할 수 있고, 이는 12의 모든 약수가 등장한다.

즉, 두 수의 곱으로 나타내어 약수를 등장시키면 된다. 또한 a*b=c일 때 a*a <= c일때까지만 수행하면 된다.

 

12의 약수는 1, 2, 3, 4, 6, 12다. 즉, 1의 등장 횟수, 2의 등장횟수 ... 12의 등장 횟수를 세어주면 된다. 최종적으로 자기 자신을 한번 세었기 때문에 나중에 1을 빼주면 된다.

 

배열의 각 원소가 몇 개 등장했는지 세고, 각 원소의 약수를 구하여 해당 약수가 몇 번 등장했는지 세면 된다.

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
#include <map>
#include <set>
#include <string>
#define INF 987654321
#define lld long long
#define MAX_N 1000001

using namespace std;

int arr[MAX_N];

bool customCompare(const pair<int, int>& a, const pair<int, int>& b) {
	return a.second < b.second;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin >> n;
	vector<int> v(n);
	vector<int> mat(1000001);
	vector<int> result(n);
	for(int i = 0; i < n; i++) {	
		int x; cin >> x;
		v[i] = x;
	}
	for (size_t i = 0; i < n; i++)
	{
		mat[v[i]]++;
	}
	
	for(int i = 0; i < n; i++) {
		int t = 1;
		while(t*t <= v[i]) {
			if(v[i] % t == 0) {
				if(t*t != v[i]) {
					result[i] += mat[t] + mat[(int)(v[i]/t)];
				} else {
					result[i] += mat[t];
				}
			}
			t++;
		}
	}

	for(int i = 0; i < n; i++) {
		cout << result[i]-1 << '\n';
	}

	return 0;
}