U E D R , A S I H C RSS

Ugly Numbers/강희경

어글리 넘버는 결국 이전의 어글리넘버(seed) * 2 or * 3 or * 5라는 생각으로
넉넉한(답을 이미 알기에 ㅎㅎ) 싸이즈의 불리언맵핑 배열을 만들어
어글리한지 확인하려는 수의 seed가 어글리했는지를 확인하는 방법으로
서치 시간을 엄청나게 줄였다고 자부했는데...
결과는...망했음.
#include<iostream>
using namespace std;

#define RANK 1500
#define MAX 999999999

bool uglyMap[MAX];

bool isUgly(int number){
	if(number%2 == 0){
		number/=2;
	}
	else if(number%3 == 0){
		number/=3;
		
	}
	else if(number%5 == 0){
		number/=5;
	}
	else{
		return false;
	}

	if(uglyMap[number] == true)
		return true;
	else
		return false;
}

int main(){
	//for(int i = 0; i < MAX; i++)
	//	uglyMap[i] = false;
	uglyMap[1] = true;
	uglyMap[2] = true;
	uglyMap[3] = true;
	uglyMap[4] = true;
	uglyMap[5] = true;
	
	int count = 5;
	int number = 5;
	while(count < RANK){
		number++;
		if(isUgly(number)){

			uglyMap[number] = true;
			count++;
		}
	}
	cout << number;
	return 0;
}
/*
#include<iostream>
using namespace std;

bool isUgly(int number){
	while(number%2 == 0){
		number /= 2;
		if(number == 1)
			return true;
	}
	while(number%3 == 0){
		number /= 3;
		if(number == 1)
			return true;
	}
	while(number%5 == 0){
		number /= 5;
		if(number == 1)
			return true;
	}
	return false;
}

int main(){
	int count = 1;
	int number = 1;
	while(count < 100){
		number++;
		if(isUgly(number)){	
			count++;
		}
	}
	cout << number;
	return 0;
}*/
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:28:19
Processing time 0.0150 sec