[Algorithm] C++ Ugly Numbers (투포인트 알고리즘)

입력예제 1

10

 

출력예제 1

1500

 

입력예제 2

1500

 

출력예제 2

859963392

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<algorithm>

using namespace std;
int a[1501];
int main() {
	int n, i, p2, p3, p5, min = 2147000000;
	scanf("%d", &n);
	a[1] = 1;
	p2 = p3 = p5 = 1;
	for (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\n", a[n]);
	return 0;
}