34. UVa-10976 Fractions Again?! //느린 배열?

문제

<그림1: 문제 설명>

문제 자체는 쉽다 자연수 k가 주어졌을 때 1/k = 1/x + 1/y 를 만족하는 자연수 쌍(x,y)를 찾는 것이다. (대칭 해 제외)

Sample Output을 보면 search space에 대해 어느정도 줄일 수 있는 IDEA를 얻을 수 있는데 다음 그림을 보자.

 

<그림2: y의 특성>

12가 k로 주어졌을 때 y를 보면 k+1부터 2*k까지이다.

사실 생각해보면 x나 y중 하나의 수는 k보다 작거나 같아질 수 없다.(부등식을 생각해보자) 또한 대칭해 제외이니까 2k보다 큰 해는 볼 필요 없다. 따라서 search space의 특성을 반영하여 해를 구하는 프로그램을 짜보면 다음과 같다.

 

//CORRECT SOL
#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;
int main() {
	
	int k;
	while (cin >> k) {
		vector<pair<int, int> > sols;
		for (int i = k + 1; i <= 2 * k; i++) {	//i is y
			if ((k * i)%(i-k)==0) {	//if integer
				sols.push_back(make_pair(k*i/(i-k),i));
			}
		}			
		cout << sols.size() << endl;
		for (int i = 0; i < sols.size(); i++) {
			printf("1/%d = 1/%d + 1/%d\n",k,sols[i].first,sols[i].second);
		}

	}

	return 0;
}

 

그런데 사실 처음에는 이렇게 안 짜고 배열이 더 빠를 거라고 생각해서 다음과 같이 짰더니 TLE가 나왔다.

 

//TLE SOLUTION
#include<cstdio>
int x[5001];
int y[5001];
int main() {

	int Count, k;
	while (scanf("%d", &k)) {
		Count = 0;
		for (int i = k + 1; i <= 2 * k; i++) {	//i가 y에 들어갈 것
			if ((k * i)%(i-k)==0) {	//만약 정수면
				x[Count] = k * i / (i - k);
				y[Count] = i;
				++Count;
			}
		}			
		printf("%d\n", Count);
		for (int i = 0; i < Count; i++) {
			printf("1/%d = 1/%d + 1/%d\n",k,x[i],y[i]);
		}

	}

	return 0;
}

그런데 TLE떠서 해를 저장하는 공간만 vector로 바꿔보니 오히려 vector가 빨랐다.

배열이 크기가 커지면 cache활용도가 낮아지는 걸까? 더 빠를거라고 생각했던 배열은 훨씬훨씬 느렸다.

다음은 실제로 계속 sol을 고치다가 저장공간만 바꿨을 때 바뀐 판정이다. 정말 알다가도 모를 하드웨어의 세계다.

크기가 큰 배열을 쓸 때는 TLE의 가능성을 염두해야하는 것 같다..