백준 2839, 4948 java

2839 설탕배달

public class Hello {
    public static double over = 1e9;

    public static double dp(double[] dp_list, int i) {
        if (i <= 2) return over;
        if (dp_list[i] != 0) return dp_list[i];

        dp_list[i] = Math.min(dp(dp_list, i - 3), dp(dp_list, i - 5)) + 1;
        return dp_list[i];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int i = Integer.parseInt(br.readLine());

        double[] dp_list = new double[i + 1];
        dp_list[3] = 1;
        if (i >= 5) dp_list[5] = 1;
        double res = dp(dp_list, i);

        if (res >= over) System.out.println(-1);
        else System.out.println((int) res);
    }
}

dp나 greedy로 풀 수 있다.

4948 베르트랑 공준

public class Prime {
    public static int[] prime = new int[246914];

    public static boolean getPrime(double num) {
        int memory = prime[(int) num];
        if (memory == -1) return false;
        if (memory == 1) return true;

        double num_sqrt = Math.floor(Math.sqrt(num));
        for (double i = 2; i <= num_sqrt; i++) {
            if (num % i == 0) {
                prime[(int) num] = -1;
                return false;
            }
        }
        prime[(int) num] = 1;
        return true;
    }

    public static void main(String[] args) throws IOException {
//        System.out.println(Arrays.toString(prime));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        while (n != 0) {
            int count = 0;
            for (double i = n + 1; i <= 2 * n; i++) {
                if (getPrime(i)) count++;
            }
//            System.out.println(count);
            sb.append(count).append("\n");
            n = Integer.parseInt(br.readLine());
        }
        System.out.print(sb);
    }
}

입력이 한번에 들어옴을 주의하자.
에라토스테네스의 체를 사용하지 않아도 통과된다.
그러나 dp활용 안하면(기존 결과를 기억하지 않으면) 시간초과가 나온다.

입/출력은 BufferedReader/Writer 사용하는게 가장 좋다고 한다.