이코테 - 못생긴 수 with JAVA

 

 

해결

못생긴 수는 2,3,5만을 약수로 갖는 수들을 의미한다.

따라서, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15 순서대로 이루어진다.

중요한 것은 못생긴수는 못생긴수에 2, 3, 5를 곱한 결과로 이루어진다는 것이다.

 

문제에서 1은 못생긴 수라고 주어진다.

1

1x2, 1x3, 1x5

= [1, 2, 3, 5]

2

2x2, 2x3, 2x5

= [1, 2, 3, 5, 4, 6, 10] = [1, 2, 3, 4, 5, 6, 10]

3

3x2, 3x3, 3x5

 = [1, 2, 3, 4, 5, 6, 9, 10, 15]

 

 

 

 

코드

import java.util.*;

public class Q5 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n];
        dp[0] = 1;

        // 다음에 곱해야할 dp 인덱스
        int index2 = 0;
        int index3 = 0;
        int index5 = 0;

        // 다음 dp에 들어가게될 값
        int value2 = 2;
        int value3 = 3;
        int value5 = 5;

        for(int i=1; i<n; i++){
            dp[i] = Math.min(value2, value3);
            dp[i] = Math.min(dp[i], value5);

            // if문만을 사용해 겹치는 수에 대한 대비
            if(dp[i] == value2){
                index2 += 1;
                value2 = dp[index2]*2;
            }

            if(dp[i] == value3){
                index3 += 1;
                value3 = dp[index3]*3;
            }

            if(dp[i] == value5){
                index5 += 1;
                value5 = dp[index5]*5;
            }
        }
        System.out.println(dp[n-1]);
    }
}