3501번 - 최대공약수 맞추기 게임 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 129 | 46 | 41 | 46.067% |
문제
상근이와 정인이는 숫자 맞추기 게임을 하고 있다.
먼저, 정인이는 1보다 크거나 같고, n보다 작거나 같은 자연수 하나를 생각한다.
상근이는 1보다 크거나 같고, n보다 작거나 같은 자연수 x를 정해 정인이에게 생각한 숫자가 x인지 물어볼 수 있다. 이때 정인이는 자신이 생각한 숫자와 x의 최대공약수가 몇 인지 말해준다.
다음은 n=6일 때 가능한 상근이와 정인이의 대화이다.
- 상근: 3이야?
- 정인: 3이랑 내가 생각한 숫자의 최대공약수는 1이야.
- 상근: (음... 그럼 3이랑 6은 아니네? 근데 1,2,4,5는 될 수 있어!) 그럼 2야?
- 정인: 2랑 내가 생각한 숫자의 최대공약수는 2야.
- 상근: (오!? 그럼 1, 5는 아니겠네?) 너가 생각한 숫자는 4야 맞지?
- 정인: 4랑 내가 생각한 숫자의 최대공약수는 2야.
- 상근: 그럼 니가 생각한 숫자는 2네 ㅋㅋㅋ
위의 예에서 상근이는 정인이가 생각한 숫자를 맞추기 위해서 질문을 총 3번 했다. 하지만, n=6인 경우에 항상 2번의 질문으로 정인이가 생각한 숫자를 맞출 수 있다.
제일 먼저 상근이는 6을 물어보면 된다. 만약 정인이가 1이라고 대답했다면, 정인이가 생각한 숫자는 1과 5중 하나이기 때문에, 2번 질문으로 맞출 수 있다. 정인이의 대답이 2라면, 정인이가 생각한 숫자는 2와 4중 하나이다. 만약, 정인이가 3이라고 대답했다면, 정답은 3이고, 6이라고 대답했다면 6이다.
따라서, 상근이는 최대 2번의 질문으로 정인이가 생각한 숫자를 맞출 수 있다.
n이 주어졌을 때, 상근이가 최적의 방법으로 질문했을 때, 최대 몇 번 만에 정인이가 생각한 숫자를 맞출 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 n이 주어진다. 2 ≤ n ≤ 10,000
출력
첫째 줄에 상근이가 최적의 방법으로 질문했을 때, 최대 몇 번의 질문으로 정인이가 생각한 숫자를 맞출 수 있는지 출력한다.
예제 입력 1
6
예제 출력 1
2
출처
ICPC > Regionals > Northern Eurasia > Northern Eurasia Finals > NEERC 2011 G번
- 문제의 오타를 찾은 사람: BaaaaaaaaaaarkingDog
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호