[이코테][Java] 못생긴 수

문제 설명

못생긴 수란 오직 2, 3, 5만을 소인수로 가지는 수를 의미한다.(즉, 오직 2, 3, 5를 약수로 가지는 합성수)

1은 못생긴  수라고 가정하고, 못생긴 수들은 {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...} 순으로 이어지게 된다. 이 때, n번째 못생긴 수를 찾느 ㄴ프로그램을 작성하세요.

 

입력조건

• 첫째 줄에 n

출력조건

• n번째 못생긴 수 출력

입출력 예시

• 입력예시	출력예시
  10	12
  4	4

 

 

 

 

문제 풀이

• 다이나믹 프로그래밍 풀이
• 못생긴 수에 각각 2의 배수, 3의 배수, 5의 배수를 곱한 값도 못생긴 수가 된다.
• 예를 들면, 문제에서 1, 2, 3, 5 는 못생긴 수 임을 알 수 있다. 이 때 각 못생긴 수에 2의 배수, 3의 배수, 5의 배수를 구하면 다음과 같다.

  못생긴 수	배수한 값	전체 못생긴 수
  못생긴 수 1	1x2, 1x3, 1x5	{1, 2, 3, 5}
  못생긴 수 2	2x2, 2x3, 2x5	{1, 2, 3, 4, 5, 6, 10}
  못생긴 수 3	3x2, 3x3, 3x5	{1, 2, 3, 4, 5, 6, 9, 10, 15}
  못생긴 수 4	4x2, 4x3, 4x5	{1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 20}

• 이렇게 오름차순으로 못생긴 수를 하나씩 확인하면서 각각 2 or 3 or 5를 곱한 값도 못생긴 수가 될 수 있다.
• 여기서 못생긴 수를 오름차순으로 담는 방법은 2의 배수, 3의 배수, 5의 배수 한 값들 중에서 가장 작은 값을 고르면 된다. 

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

        int[] ugly_dp = new int[n]; //못생긴 수를 담는 dp 테이블
        ugly_dp[0] = 1; //1은 못생긴 수

        //각각 2, 3,5배 인덱스
        int index2 = 0, index3 = 0, index5 = 0;
        //처음 곱셈 값 초기화
        //여기서 value2 = ugly_dp[0]*2, value3 = ugly_dp[0]*3, value5 = ugly_dp[0]*5
        int value2 = 2, value3 = 3, value5 = 5;


        for (int i = 1; i < n; i++) {
        	//2의 배수, 3의 배수, 5의 배수인 못생긴 수 중에서 가장 작은 값
            ugly_dp[i] = Math.min(value2, Math.min(value3, value5));

            //만약 ugly_dp[i] 값이 각 배수를 곱한 값과 같다면, 해당 배수결과값 증가
            if (ugly_dp[i] == value2) {
                index2++;
                value2 = ugly_dp[index2] * 2;
            }
            if (ugly_dp[i] == value3) {
                index3++;
                value3 = ugly_dp[index3] * 3;
            }
            if (ugly_dp[i] == value5) {
                index5++;
                value5 = ugly_dp[index5] * 5;
            }
        }

        System.out.println(ugly_dp[n - 1]);
    }
}

 

처음에 작은 순서대로 하나씩 못생긴 수를 직접 구해보면서 '못생긴수 A = 못생긴수 B * (2 or 3 or 5)'인 것을 파악했다. 

여기에서 못생긴 수를 오름차순으로 담아야 하기 때문에 2, 3, 5를 곱하는 순서에 규칙이 있을 것이라 생각하고 문제를 풀려고 했더니 어렵게 느껴진 것 같다.

---

[참고서적]

이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈