Ugly Numbers/송지원

#include <iostream>
using namespace std;

const int MAX = 1500;
int uglyNum(int);


void main(){
	int num;
	cin >> num;
	cout << "The " << num << "th ugly number is " << uglyNum(num) << endl;
}

int uglyNum(int num){
	int ugly[MAX];
	int n2, n3, n5; // ugly number��� 2,3,5��� ���한 ���
	int i2, i3, i5;
	
	ugly[0] = 1;

	n2 = 1;
	n3 = 1;
	n5 = 1;
	
	i2 = 0;
	i3 = 0;
	i5 = 0;

	for(int i=1;i<num;i++){
		n2 = ugly[i2]*2;
		n3 = ugly[i3]*3;

		if(n2 == n3){
			i3++;
			n3 = ugly[i3]*3;
		}
		
		n5 = ugly[i5]*5;
		
		if(n2 == n5 || n3 == n5){
			i5++;
			n5 = ugly[i5]*5;
		}
		if(n2 < n3 && n2 < n5){
			ugly[i] = n2;
			i2++;
		}
		else if(n3 < n2 && n3 < n5){
			ugly[i] = n3;
			i3++;
		}
		else{
			ugly[i] = n5;
			i5++;
		}
	}

	return ugly[num-1];
}