백준 27650 - 마법박스

https://www.acmicpc.net/problem/27650

27650번: 마법박스

헷갈리는 입출력 방식은 차치하자. 먼저 문제에서 묻는 바가 무엇인지부터 이해해야 한다. 문제 난이도가 올라갈 수록 이게 더 어려워지는 것 같다.

 

무지가 찾는 수는 박스에 들어있지 않은 가장 작은 소수이다. 만약 N보다 작으면서 소수가 아닌 수가 박스에 들어있지 않다면, ex) 49 마법박스의 성질에 따라 그 수를 소인수분해한 결과 역시 박스에 들어있으면 안 된다. ex) 7 따라서 찾는 수는 반드시 소수이다.

 

2부터 500만까지의 정수 중 소수의 개수가 못해도 10만개는 될 것이다. 프로그램이 2, 3, 5, ... 오름차순으로 질문했다가는 100도 가기 전에 프로그램이 종료된다. 백준 좀 치는 사람들은 여기서 이분탐색을 떠올렸을 것이고, 나같은 약자들은 밑의 '알고리즘 분류'를 읽고 이분탐색을 적용해보면 된다.

 

우리의 응답이 1일 경우 i까지의 정수는 모두 존재한다는 뜻이므로 범위의 오른쪽을 탐색하고, 0일 경우 왼쪽이나 현재 위치에 존재하지 않는 정수가 있다는 뜻이므로 범위의 왼쪽을 탐색하면 된다.