UVa 136 - Ugly Numbers

Joonas' Note

UVa 136 - Ugly Numbers 본문

알고리즘/문제 풀이

UVa 136 - Ugly Numbers

2020. 7. 6. 16:32 joonas 읽는데 2분
  • 문제
  • 풀이
  • 코드

문제

소인수가 2 또는 3 또는 5로만 이루어진 수를 "못생긴 수"라고 했을 때, N번째 못생긴 수를 출력하는 문제이다.

New Zealand 1990 Division I에 등장했던 문제로, 여러 저지에서 풀어볼 수 있다.

풀이

한 장 요약

빨간색을 현재까지 살펴본 수, 파란색을 앞으로 살펴볼 수라고 했을 때 그림을 위와 같다.

파란색으로 색칠된 수 중에서 가장 작은 수부터 순서대로 살피면, 그 순서대로 N번째 못생긴 수가 결정된다. 이는 다익스트라 알고리즘에서 그림이 어떻게 그려지는 지를 떠올리면 이해가 쉽다.

수의 중복을 제거하기 위해서 이전에 5를 곱해서 만들어진 수에는 2나 3을 곱하지 않았다. 2*5 = 5*2 이기 때문에 순서상 2*5가 먼저 만들어지기 때문이다.

코드

 

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef long long lld;
struct node {
node(lld d, int p) : data(d), prev(p) {}
lld data;
int prev;
bool operator < (const node& p) const {
return data > p.data;
}
};
int main() {
priority_queue<node> pq;
pq.push(node(1, 0));
int mul[] = { 2, 3, 5 };
vector<lld> v;
while (v.size() < 1500) {
node c = pq.top();
pq.pop();
v.push_back(c.data);
for (int i = c.prev; i < 3; ++i) {
lld x = c.data * mul[i];
pq.push(node(x, i));
}
}
for (int n; ~scanf("%d", &n) && n;) {
printf("%lld\n", v[n - 1]);
}
return 0;
}