[알고리즘 연습] Ugly Numbers

Ugly Numbers

• 어떤 수를 소인수분해 했을 때 그 소인수가 2 또는 3 또는 5로만 이루어진 수를 'Ugly Number'라고 부른다. (1포함)
• ex. 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
• N번째 Ugly Number를 출력하는 프로그램을 작성하시오.

---

풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
​​​​int n, i, p2=0, p3=0, p5=0, minValue;

​​​​cin >> n;

​​​​vector<int> a(n);

​​​​a[0] = 1;

​​​​for(i=1; i<n; i++) {
​​​​​​​​minValue = min(min(a[p2]*2,a[p3]*3),a[p5]*5);
​​​​​​​​if (minValue == a[p2]*2) p2++;
​​​​​​​​if (minValue == a[p3]*3) p3++;
​​​​​​​​if (minValue == a[p5]*5) p5++;
​​​​​​​​a[i] = minValue;
​​​​}

​​​​cout << a[n-1];

​​​​return 0;
}

• 모든 숫자를 체크하는 방법은 너무 비효율적이다.
• 따라서 기준이 되는 수인 2, 3, 5를 기반으로 하나씩 체크하고 채워나간다.
• 투포인터 알고리즘의 응용버전이라고 생각하자.