[알골90제] 52번 - Ugly Numbers : 투포인트 알고리즘 응용

* 문제 

- 어떤 수를 소인수분해 했을 때 그 소인수가 2 또는 3 또는 5로만 이루어진 수를 Ugly Number

- Ugly Number를 차례대로 적어보면 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, .......입니다. 숫자 1은 Ugly Number의 첫 번째 수

- 자연수 N이 주어지면 Ugly Number를 차례로 적을 때 N번째 Ugly Number를 구하는 프로그램 작성

 

입력

10

 

출력

12

 

 

* 생각

- N이 입력되면 1부터 무한루프까지 각각 소인수분해해서 2, 3, 5 로만 떨어지면 count++하고, count가 15 즉, N이 되면 while문을 빠져나와서 해당 X수를 적는다. => 시간이 너무 오래걸림...time limited!

- 소인수 분해하는 과정??

 

 

* 풀이방법 

- 투포인트 알고리즘이지만 3개를 쓴다! (해외 알고리즘 인터뷰 문제로도 많이 나옴)

- a[N]에는 N번째 어글리넘버 값이 들어가 있다.

- p2, p3, p5는 모두 1로 초기화, 포인터 역할이기 때문에 최초에 1을 가리키고 있음

(어글리넘버가 소인수가 2,3,5로만 이루어져있는 것이라 2,3,5로 함)

- 한번 for문이 돌 때마다 아래 연산을 진행한다.

 

 

 

 

 

 

 

- 연산 후 가장 작은 값을 그 다음 배열칸에 넣고, 해당되는 값을 증가시켜준다.

ex. 최초에 a[p2], a[p3], a[p5]은 모두 a[1], a[1], a[1]이기 때문에 a[1]에는 1값이 들어가있어서

각각 2, 3, 5를 곱하면 p2가 제일 수가 작은 값이다. 그렇기 때문에 a[p2]*2 = 2값을 a[2]에 넣고,

p2는 2로 바꾼다. a[p2] == a[2] 이며 값은 2를 가지고 있는 것으로 된다.

 

 

- 아래의 경우 6 6으로 같은 숫자가나와서 최소값을 둘다로 지정하고, p2 p3를 둘다 증가 시켜줘야 한다.

- a[10] = 12 답

 

- 왜 a행렬에 있는 숫자들은 2,3,5로만 이루어진 줄 알까?

1부터 시작해서 2,3,5를 계속 곱해서 나가고 있으니 소인수가 2,3,5가 나올 수 밖에 없다!

 

 

 * 코드 구현

 

// 52번 - 투포인트 알고리즘 응용

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int a[1501];

int main() {

	int n, p2, p3, p5, min = 999999999;
	scanf("%d", &n);

	a[1] = 1;
	p2 = p3 = p5 = 1;

	for (int i = 2; i <= n; i++) {
	
		if (a[p2] * 2 < a[p3] * 3) min = a[p2]*2;
		else min = a[p3]*3;
		if (a[p5] * 5 < min) min = a[p5]*5;

		if (a[p2] * 2 == min) p2++;
		if (a[p3] * 3 == min) p3++;
		if (a[p5] * 5 == min) p5++;

		a[i] = min;
	}
	printf("%d", a[n]);
}