35.못생긴 수

📍 문제 설명

못생긴 수란 오직 2, 3, 5 만을 소인수로 가지는 수를 의미한다. 다시 말해 오직 2, 3, 5를 약수로 가지는 합성수를 의미한다. 1은 못생긴 수라고 가정한다. 따라서 못생긴 수들은 {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... } 순으로 이어지게 된다. 이 때, n번째 못생긴 수를 찾는 프로그램을 작성해라. 예를 들어 11번째 못생긴 수는 10이다.

입력조건

• 첫째 줄에 n이 입력된다.(1 <= n <= 1,000)

출력조건

• n번째 못생긴 수를 출력한다.

💡 접근

못생긴 수를 담기위한 dp 테이블을 초기화한다.

ugly[0] = 1이고

ugly[1] = next2 = 2

ugly[1] == next2 이므로 i2 += 1; next2 = ugly[1] * 2 = 4 4,3,5

ugly[2] = next3 = 3

ugly[2] == next3 이므로 i3 += 1; next3 = ugly[1] * 3 = 3 4,3,5

ugly[3] = next2 = 4

ugly[3] == next2 이므로 i2 += 1; next2 = ugly[2] * 2 = 6 6,6,5

ugly[4] = next5 = 5

ugly[4] == next5 이므로 i5 += 1; next5 = ugly[1] * 5 = 10 6,6,10

ugly[5] = next2 = next3 = 6

ugly[5] == next2, next3 이므로

i2 += 1; next2 = ugly[3] * 2 = 8

i3 += 1; next3 = ugly[2] * 3 = 9 8,9,10

...

 

👩‍💻 코드

import java.util.*;

public class Main {

    static int n;
    static int[] ugly = new int[1000]; // 못생긴 수를 담기 위한 테이블 (1차원 DP 테이블)

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        // 2배, 3배, 5배를 위한 인덱스
        int i2 = 0, i3 = 0, i5 = 0;
        // 처음에 곱셈 값을 초기화
        int next2 = 2, next3 = 3, next5 = 5;

        ugly[0] = 1; // 첫 번째 못생긴 수는 1
        // 1부터 n까지의 못생긴 수들을 찾기
        for (int l = 1; l < n; l++) {
            // 가능한 곱셈 결과 중에서 가장 작은 수를 선택
            ugly[l] = Math.min(next2, Math.min(next3, next5));
            // 인덱스에 따라서 곱셈 결과를 증가
            if (ugly[l] == next2) {
                i2 += 1;
                next2 = ugly[i2] * 2;
            }
            if (ugly[l] == next3) {
                i3 += 1;
                next3 = ugly[i3] * 3;
            }
            if (ugly[l] == next5) {
                i5 += 1;
                next5 = ugly[i5] * 5;
            }
        }

        // n번째 못생긴 수를 출력
        System.out.println(ugly[n - 1]);
    }
}