52. Ugly Numbers (투포인트 알고리즘 응용) [정렬 & 이분탐색(결정알고리즘) & 투포인트 알고리즘 & 스택]

나의정답.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);

	int n, p2 = 1, p3 = 1, p5 = 1, min = -1;
	scanf("%d", &n);
	// 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36
	int* arr = new int[1502];
	arr[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (arr[p2] * 2 < arr[p3] * 3) min = arr[p2] * 2;
		else min = arr[p3] * 3;
		if (arr[p5] * 5 < min) min = arr[p5] * 5;
		if (min == arr[p2] * 2) p2++;
		if (min == arr[p3] * 3) p3++;
		if (min == arr[p5] * 5) p5++;
		arr[i] = min;
	}

	printf("%d ", arr[n]);
	
	delete[] arr;
}