U E D R , A S I H C RSS

Ugly Numbers/송지훈

설명

  • 조낸 간단함. 1500개짜리 배열이 꽉 찰때까지 1부터 시작해서
쭉 훑으면서 찾는 방식.
  • 2, 3, 5의 배수라는 점에 착안해서 코딩.

소감

정말 좋지 않은 코드. 900번째까지 구하는데 2 초걸리고,
1000번째까지 구하는데 7초 걸린다...

1500번째꺼 구하도록 했더니... 76초 걸린다...

#include <iostream>
#include <ctime>
using std::cout;
using std::cin;
using std::endl;
using std::clock_t;

#define LIMIT 1500                      // 배열 한계수

int main() {
	int arr[LIMIT] = {0}, num, index = 0, target;
	clock_t start,end;              // 수행시간 구할 때 쓰려고 넣은 변수.
	target = 1500;                  // 1500번째 수를 구하도록 할 때 쓰는 변수.

	start = clock();                // 시작한 시간.
	for(int i = 1;arr[target-1] == 0;i++) {
		num = i;
		while((num % 2) == 0) {
			num /= 2;
		}
		while((num % 3) == 0) {
			num /= 3;
		}
		while((num % 5) == 0) {
			num /= 5;
		}
		if(num == 1) {          // 2, 3, 5 로 나눴는데 몫이 1이면 못난이수.
			arr[index] = i; // 몫이 1이 아니면 그냥 잡수.
			index++;
		}
	}
	end = clock();                  // 끝난 시간.

	cout << "Run time = " << (double)(end-start)/CLK_TCK << endl
		 << arr[target-1] << endl;
	return 0;
}

느낀 점

다른 방식의 알고리즘으로 그냥 막 배열에 때려넣은 뒤
sorting 을 사용하는 방법을 생각해봐야 하겠다 라는 것을 느낌.

사실 처음부터 정렬을 써야겠다고 생각했으나
도무지 방법이 생각이 안남.

2, 3, 5의 거듭제곱꼴이라는 것에 착안해서 지수에서 어떤 법칙을 찾아내려고 했으나
30개까지 구해봐도 법칙을 못찾아서 그냥 위의 방법으로 구했음...


보창이형 코드보니 지수를 써서 하는 방법이 있는거 같은데
자세히 보진 않았지만 그냥 막 때려넣지 않았나... 하는 생각이...
결국 퀵 소트로 정렬하신 듯 한데...

아... 괜히 어렵다.
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.1030 sec