Today
38
Total
243,765
Notice
Recent Posts
Recent Comments
«   2022/08   »
일 월 화 수 목 금 토
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      
Archives
관리 메뉴

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가 먼저 만들어지기 때문이다.

    코드

     

     

    반응형
    저작자표시

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

    BOJ 13976 - 타일 채우기 2  (0) 2021.09.07
    BOJ 2133 - 타일 채우기  (0) 2021.09.07
    UVa 136 - Ugly Numbers  (2) 2020.07.06
    BOJ 11012 - Egg  (1) 2020.06.10
    [코딩으로 풀어보기] 95화 4번, 1~9까지 숫자로 식을 성립시켜라.  (0) 2020.06.10
    BOJ 3640 - 제독  (0) 2020.05.24
    Tag
    , , , , , , , ,
    '알고리즘/문제 풀이' Related Articles more
    2 Comments
    • 프로필사진 도움 2020.11.07 15:22 컴퓨터에서 들리는 소리 영어를 자막화해서 보여주는 프로그램(google STT) 만드셨던 거 사용가능할까요? 줌으로 외국인과 대화할 때 영어자막이 뜨면 좋겠어서요.
      이메일 주세요 dlwjdduqdjeldp@gmail.com
      댓글 메뉴 보기
      댓글메뉴
      댓글주소 수정/삭제 댓글쓰기
    • 프로필사진 BlogIcon joonas 2020.11.10 20:56 신고 서비스를 종료했던 Speech Translator 확장 프로그램의 경우, 현재 오픈소스로 전환하여 모든 분들이 사용할 수 있는 형태로 변경하였습니다.

      확장 프로그램은 zip 파일을 크롬에 그대로 설치하시면 되고,
      API 서버의 경우 Google Cloud Platform과의 연동을 통해 서비스를 그대로 사용하실 수 있습니다.

      이 과정에서 과금이 발생할 수 있으니 유의하시면 좋겠습니다.
      댓글 메뉴 보기
      댓글메뉴
      댓글주소 수정/삭제
    댓글쓰기 폼
    Prev 1 2 3 4 5 6 7 ··· 64 Next