Ugly Numbers/송지원

풀이+잡담 ¶

희경 오빠가 쉬울거라고 한 말만 믿다가 피토했습니다. (워낙 이런 문제풀기에 약해서..)
게다가 처음에는 알고리즘을 잘못 이해해서 완전 잘못짜는 바람에.. 갈아 엎어버렸어요=_=

어떻게 찌끄려줘야할까 고민해봤는데..

배열에 2,3,5 인수로 이루어진 수를 하나씩 때려넣어 sort를 할까 하다가
1500개짜리 배열을 매번 sort해줄 수가 없으니ㅡㅡ;;
기존 ugly number에다가 2,3,5를 곱해도 ugly number가 될 것이니
그걸 비교해가면서 배열에 집어넣어보자 식으로 도전했습니다.

와 빠르네 정모 때 설명부탁해요.ㅎㅎ --강희경

[edit]

소스 ¶

#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];
}