UVa 136 - Ugly Numbers
Joonas' Note
UVa 136 - Ugly Numbers 본문
- 문제
- 풀이
- 코드
문제
소인수가 2 또는 3 또는 5로만 이루어진 수를 "못생긴 수"라고 했을 때, N번째 못생긴 수를 출력하는 문제이다.
New Zealand 1990 Division I에 등장했던 문제로, 여러 저지에서 풀어볼 수 있다.
풀이
![](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
빨간색을 현재까지 살펴본 수, 파란색을 앞으로 살펴볼 수라고 했을 때 그림을 위와 같다.
파란색으로 색칠된 수 중에서 가장 작은 수부터 순서대로 살피면, 그 순서대로 N번째 못생긴 수가 결정된다. 이는 다익스트라 알고리즘에서 그림이 어떻게 그려지는 지를 떠올리면 이해가 쉽다.
수의 중복을 제거하기 위해서 이전에 5를 곱해서 만들어진 수에는 2나 3을 곱하지 않았다. 2*5 = 5*2 이기 때문에 순서상 2*5가 먼저 만들어지기 때문이다.
코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
'알고리즘 > 문제 풀이' 카테고리의 다른 글
BOJ 13976 - 타일 채우기 2 (0) | 2021.09.07 |
---|---|
BOJ 2133 - 타일 채우기 (0) | 2021.09.07 |
BOJ 11012 - Egg (1) | 2020.06.10 |
[코딩으로 풀어보기] 95화 4번, 1~9까지 숫자로 식을 성립시켜라. (0) | 2020.06.10 |
BOJ 3640 - 제독 (0) | 2020.05.24 |