Ugly Numbers/곽세환

소감 2 ¶

통과O

숫자 하나하나를 일일이 나눠보는건 시간이 많이 걸린다. 그래서 다른 방식으로 접근.
STL사용하니 한결 간편하다
답은 The 1500'th ugly number is <숫자>. 형식이어야 한다.

소스 2 ¶

~cpp 
//136
#include <iostream>
#include <list>
using namespace std;

void main()
{
	int cnt = 1500;
	list<unsigned int> numbers;
	numbers.push_back(1);
	unsigned int temp;

	while (cnt)
	{
		temp = numbers.front();
		numbers.pop_front();
		cnt--;
		numbers.push_back(temp * 2);
		numbers.push_back(temp * 3);
		numbers.push_back(temp * 5);
		numbers.sort();
		numbers.unique();
	}

	cout << "The 1500'th ugly number is " << temp << "." << endl;
}

소감 1 ¶

통과X
1500번째 구하는데 2분정도 걸린다 ㅡ.ㅡ
생각보다 오래걸리는 이유가 뭐지...

소스 1 ¶

~cpp 
#include <iostream>
using namespace std;

void main()
{
	int cnt;
	cin >> cnt;
	
	int num = 1, temp;
	cnt--;

	while (cnt)
	{
		num++;

		temp = num;
		while (temp % 2 == 0)
			temp = temp / 2;
		while (temp % 3 == 0)
			temp = temp / 3;
		while (temp % 5 == 0)
			temp = temp / 5;
		
		if (temp == 1)
			cnt--;
	}

	cout << num << endl;
}

댓글 ¶

UglyNumbers