UglyNumbers/송지원 - Revision history

imported>rkd49 at 04:26, 19 September 2008

2008-09-19T04:26:22Z

← Older revision		Revision as of 04:26, 19 September 2008
Line 11:		Line 11:
	기존 ugly number에다가 2,3,5를 곱해도 ugly number가 될 것이니		기존 ugly number에다가 2,3,5를 곱해도 ugly number가 될 것이니
	그걸 비교해가면서 배열에 집어넣어보자 식으로 도전했습니다.		그걸 비교해가면서 배열에 집어넣어보자 식으로 도전했습니다.
			와 빠르네 정모 때 설명부탁해요.ㅎㅎ --[[강희경]]

	== 소스 ==		== 소스 ==

imported>enochbible at 13:49, 16 September 2008

2008-09-16T13:49:05Z

← Older revision		Revision as of 13:49, 16 September 2008
Line 1:		Line 1:
	== 풀이+잡담 ==		== 풀이+잡담 ==

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

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

	배열에 2,3,5 인수로 이루어진 수를 하나씩 때려넣어 sort를 할까 하다가		배열에 2,3,5 인수로 이루어진 수를 하나씩 때려넣어 sort를 할까 하다가
Line 9:		Line 11:
	기존 ugly number에다가 2,3,5를 곱해도 ugly number가 될 것이니		기존 ugly number에다가 2,3,5를 곱해도 ugly number가 될 것이니
	그걸 비교해가면서 배열에 집어넣어보자 식으로 도전했습니다.		그걸 비교해가면서 배열에 집어넣어보자 식으로 도전했습니다.

	~~나름 빨리 돌아가는거 같아요.~~


	== 소스 ==		== 소스 ==

imported>enochbible at 13:47, 16 September 2008

2008-09-16T13:47:35Z

New page

== 풀이+잡담 ==

처음에는 알고리즘을 잘못 이해해서 완전 잘못짜는 바람에.. 갈아엎어버렸습니다-_-

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

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

나름 빨리 돌아가는거 같아요.

== 소스 ==

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