[자바] 백준 27650 - 마법박스 (java)

목차

문제 : boj27650

 

 

필요 알고리즘

• 매개 변수 탐색 (이분 탐색), 에라토스테네스의 체
  
  • 문제에서 제시된 것의 규칙을 찾아, 20번 내에 물어볼 수 있는 방법을 찾아야 한다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  처음엔 무지성으로 단순히 최대 500만개짜리 배열 만들어두고, 2부터 시작하면서 물어보고 1이라고 하면 2의 배수 전부 체크하는 식으로 생각했었다. 문제는 인터랙티브 문제라 틀렸습니다라고 안떴다는 점이다 ㅋㅋㅋ 그래서 맞는거 같은데 왜 틀리지?를 외치며 계속 박다가 직접 500만개 기준으로 질문을 해보니 왠걸..

 

 

  당연하게도 그렇게 해버리면 모든 소수를 다 물어보는 꼴이었다. 수학적 직관이 부족해 바로 생각하지 못한 것 같다. 최대 20번 물어볼 수 있는데, 500만 이하의 소수는 당연히 20개 초과이므로, 20번이 넘어가면서 읽을 값이 없어서 NoSuchElement가 떠버린거였다.

 

  사실 모든 소수를 다 물어본다는걸 깨달은 이상 그럼 쉬워지는데, 그냥 500만 이하의 모든 소수를 구해두고 그걸 물어보면 된다(소수를 구할 때, limit의 루트값 까지만 확인하는데 그 이유는 '이 글'에 있다). 그리고 이미 구한 소수이므로 이분 탐색으로 물어보면 된다. 이 경우 500만 이하의 소수가 2^20개 이하라면 통과 가능하므로, 무난하게 통과할 수 있다.

 

  그리고 마법박스에 들어있지 않은 '가장 작은' 수를 출력해야 하므로, 더이상 진행 불가할 때 까지 계속 물어봐야 하므로 이분 탐색을 계속하는 매개 변수 탐색으로 진행하면 된다. 말보다 코드로 보면 더 간단할 것 같다.

private void solution() {
    List<Integer> pn = initPn(sc.nextInt());	// 최대 500만 이하의 모든 소수를 구한다.

    int s = 0;
    int e = pn.size()-1;

    while (s<=e) {	// 매개변수탐색(이분탐색) 진행
        int mid = (s+e)/2;
        if (question(pn.get(mid))) e = mid-1;	// 물어본 후 답이 0이면 더 작은 소수를
        else s = mid+1;	// 답이 1이면 더 큰 소수를 물어본다.
    }
    answer(pn.get(s));	
    // 더이상 물어볼 수 없는 경우 s번째 소수가 답이다. 그리고 수학적으로 20번 이내로 항상 끝난다.
}

 

 

코드 : github

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    final Scanner sc = new Scanner(System.in);
    
    public static void main(String[] args) {
        new Main().solution();
    }

    private void solution() {
        List<Integer> pn = initPn(sc.nextInt());

        int s = 0;
        int e = pn.size()-1;

        while (s<=e) {
            int mid = (s+e)/2;
            if (question(pn.get(mid))) e = mid-1;
            else s = mid+1;
        }
        answer(pn.get(s));
    }

    private List<Integer> initPn(int limit) {
        List<Integer> pn = new ArrayList<>();
        boolean[] isPn = new boolean[limit + 1];
        int sqrtN = (int)Math.sqrt(limit);
        for (int i = 3; i <= sqrtN; i+=2) {
            if (isPn[i]) continue;
            int base = i+i;
            while (base <= limit) {
                isPn[base] = true;
                base+=i;
            }
        }
        pn.add(2);
        for (int i = 3; i <= limit; i+=2) {
            if (!isPn[i]) pn.add(i);
        }
        return pn;
    }

    private boolean question(int num) {
        System.out.println("? " + num);
        System.out.flush();
        return sc.nextInt()==0;
    }

    private void answer(int num) {
        System.out.println("! " + num);
        System.out.flush();
    }
}