[BOJ] 1124번 언더프라임 (Java)

백준 1124 언더 프라임

처음에 재귀를 활용한 조합으로 문제를 해결하려 했지만 코드가 너무 복잡해져 잘못됨을 느꼈다. 그다음엔 DP를 활용해야겠다 생각했다 주요 아이디어는 다음과 같다.

1. 에라토스테네스의 체를 활용하여 소수를 구한다.
2. DP 리스트를 만들어 해당하는 수가 소수로 나누어지는지 확인하고 i가 j로 나누어진다면, DP[i] = DP[i / j] + 1이다. 작은 수부터 탐색하기 때문에 값이 벗어나는 경우는 없다.
3. DP에 저장된 소인수 개수는 HashSet을 활용하여 소수인지 확인한다.

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

public class Main {
    public static void main(String[] args) {
        try {
            int n,m,cnt = 0;
            HashSet <Integer> hs = new HashSet<>();
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            
            // 소인수 개수를 저장할 dp 리스트
            int [] dp = new int[m + 1];
            
            // 에라토스테네스의 체를 위해 필요한 boolean 리스트
            boolean [] oTable = new boolean[m + 1];
            
            // 에라토스테네스의 체
            Arrays.fill(oTable, true);
            for(int i = 2; i <= m; i ++){
                if(oTable[i] == true){
                    hs.add(i);
                    int cur = i * 2;
                    while(cur <= m){
                        oTable[cur] = false;
                        cur += i;
                    }
                }
            }
            
            // DP 업데이트
            for(int i = 2; i <= m; i ++) {
                for (Integer j : hs) {
                    if(i % j == 0){
                        dp[i] = dp[i / j] + 1;
                        break;
                    }
                }
            }
            for (int i = n; i <= m; i++) {
                if(hs.contains(dp[i])){
                    cnt++;
                }
            }
            System.out.println(cnt);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}