관리 메뉴

Joonas' Note

UVa 136 - Ugly Numbers 본문

알고리즘/문제 풀이

UVa 136 - Ugly Numbers

joonas 2020. 7. 6. 16:32

문제

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

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

풀이

한 장 요약

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

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

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

코드

 

 

'알고리즘 > 문제 풀이' 카테고리의 다른 글

UVa 136 - Ugly Numbers  (0) 2020.07.06
BOJ 11012 - Egg  (0) 2020.06.10
[코딩으로 풀어보기] 95화 4번, 1~9까지 숫자로 식을 성립시켜라.  (0) 2020.06.10
BOJ 3640 - 제독  (0) 2020.05.24
BOJ 15480 - LCA와 쿼리  (0) 2020.05.15
BOJ 9034 - 순위  (0) 2020.05.01
0 Comments
댓글쓰기 폼