다이나믹 프로그래밍 - 5. 못생긴 수

문제

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

입력 조건: 첫째 줄에 n이 입력됩니다. (1 <= n <= 1,000)
출력 조건: n번째 못생긴 수를 출력한다.

입력 예시1
10
출력 예시 1
4

입력 예시2
12
출력 예시2
4

구현코드

import java.io.*;

public class Main{
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		// 2배, 3배, 5배 한 index 값
		int i2 = 0, i3 = 0, i5 = 0;
		// 배수 값 저장변수
		int next2 = 2, next3 =3, next5 = 5;
		int[] ugly = new int[n];
		ugly[0] = 1;
		
		for(int i = 1; i < n ; i++){
			ugly[i] = Math.min(next2, Math.min(next3, next5));
			if(ugly[i] == next2){
				i2++;
				next2 = ugly[i2] * 2;
			}
			if(ugly[i] == next3){
				i3++;
				next3 = ugly[i3] * 3;
			}
			if(ugly[i] == next5){
				i5++;
				next5 = ugly[i5] * 5;
			}
		}
		// n번째 못생긴 수를 출력
		for(int i  = 0; i < n ; i ++) {
			System.out.print(ugly[i]+" ");
		}
		 System.out.println();
        System.out.println(ugly[n - 1]);
	}
	
}

코드해석

이 문제는 1을 시작으로 2, 3, 5 를 포함한 배수들이 모두 못생긴 수 라는 것이다. 그러면 배수를 구하면 되겠네 싶을 것이다.
맞다 하지만, 오름차순으로 이루어져야 하고, 중복또한 없어야 한다.
코드를 보면 이해하기 쉽다. 값 들에 2 , 3, 5 를 곱하는데 새로만들어진 못생긴 수들 의 2, 3, 5 배 들도 못생긴 수 이기 때문에 인덱스를 가지고 구해야한다. 또한 값이 중복되지 않도록 else if 를 사용하지 않고 if 문을 사용하였다.
쉬우면서 생각하기 어려운 문제이다...