연습문제

연탄의 크기

난이도
Lv. 2
제출
3,383 명
참가자
1,249 명
정답률
37.11 %
지원 언어
C
C++
Java
Python
JavaScript
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
C 1초 1024MB
Java 1초 1024MB
Python 1초 1024MB
C++ 1초 1024MB
JavaScript 1초 1024MB

연탄을 모든 집에 배달하려고 했던 산타는 큰 고민에 빠집니다. 각 집에는 연탄 난로가 있는데, 난로와 연탄 모두 원 모양으로 되어있기 때문에 난로의 반지름의 길이가 연탄의 반지름의 길이의 배수인 집에서만 이 연탄을 사용할 수 있다는 것입니다.






n개의 집에 각각 놓여 있는 난로의 반지름의 길이가 주어졌을 때, 산타는 연탄의 반지름의 길이를 처음에 잘 설정하여 최대한 많은 집에서 이 연탄을 사용할 수 있도록 만들고자 합니다. 산타를 도와 연탄이 사용가능한 집의 수를 최대로 하는 프로그램을 작성해보세요. 단, 난로의 반지름과 연탄의 반지름은 항상 정수로 나타내지며, 연탄의 반지름은 항상 1보다 커야만 함에 유의합니다.



본 문제의 저작권은 (주)브랜치앤바운드에 있으며, 저작자의 동의 없이 무단 전재/복제/배포를 금지합니다.

제약조건

  • 1 ≤ n ≤ 100
  • 2 ≤ 난로의 반지름의 길이 ≤ 100

입력형식

첫 번째 줄에는 집의 수 n이 주어집니다.

두 번째 줄에는 각 집에 놓여 있는 난로의 반지름의 길이가 공백을 사이에 두고 주어집니다.

출력형식

연탄 사용이 가능한 최대 집의 수를 출력합니다.

입력예제1

6
2 4 6 9 12 18
출력예제1

5

첫 번째 예제에서는 연탄의 반지름의 길이를 2로 했을 때 난로의 반지름이 {2, 4, 6, 12, 18}인 집에서 모두 사용이 가능합니다. 이보다 더 많은 집이 사용하게 만들 수는 없습니다.

입력예제2

5
2 3 5 7 11
출력예제2

1

두 번째 예제에서는 연탄의 반지름의 길이를 5로 했을 때 난로의 반지름이 {5}인 집에서만 사용이 가능합니다. 이보다 더 많은 집이 사용하게 만들 수는 없습니다.

목록