2배 이상은 싫어 서브태스크 1초 256MB
문제
N 개의 막대기가 있다. 각 막대의 길이는 최대 100만이다.
길이 L 짜리 막대기를 한 번 쪼개면, L = x + y 인 두 자연수 x, y 로 만들 수 있다.
예를 들어, 길이 5 짜리 막대기는 한 번 쪼개서 ( 길이 1 & 길이 4 ) 또는 ( 길이 2 & 길이 3 ) 으로 만들 수 있다.
우리의 목표는 "한 쪽이 다른 쪽 길이의 2배 이상" 이 되는 막대기 쌍이 아예 없도록 하는 것이다.
예를 들어 [8, 9, 10, 15] 는 가능한 막대기 배열이지만 [8, 9, 10, 18] 은 불가능하다.
[8, 9, 10, 18] 에서, (8, 18) 또는 (9, 18) 막대기 쌍은 한 쪽이 다른 쪽 길이의 "2배 이상"이 되기 때문이다.
반면, [8, 9, 10, 15] 는 어떻게 두 막대기 쌍을 잡아도 한 쪽이 다른 쪽 길이의 "2배 미만"이 되어 가능하다.
이러한 조건을 만족하도록, 막대기를 쪼개는 최소 횟수를 출력하는 프로그램을 작성하자.
입력
첫 줄에 막대기 개수 N 이 입력된다. ( 1 ≤ N ≤ 20만 )
두 번째 줄에 각 막대기의 길이를 나타내는 N 개의 자연수가 "오름차순으로" 입력된다. ( 각각 1 이상 100만 이하 )
출력
첫 번째 줄에 조건을 만족하도록 막대기를 쪼개는 최소 횟수를 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 10점 | N = 2 |
| #2 | 10점 | N ≤ 10 |
| #3 | 10점 | 첫 번째 막대기의 길이는 1 이다. |
| #4 | 70점 | 제약 조건 없음 |
예제 #1
3
2 4 5
2
4 를 2 & 2 로 쪼개고,
5 를 2 & 3 으로 쪼개면,
[2, 2, 2, 2, 3] 이 되어 조건을 만족한다. 따라서 2번 쪼개면 된다.
예제 #2
5
1 2 3 4 5
10
모든 막대기의 길이가 1 이 되어야만 한다.
길이 2 짜리 막대기는 1번,
길이 3 짜리 막대기는 2번,
길이 4 짜리 막대기는 3번,
길이 5 짜리 막대기는 4번 쪼개야 한다.
따라서 총 횟수는 1 + 2 + 3 + 4 = 10 번이다.
예제 #3
5
10 10 10 10 10
0
이미 조건을 만족하기 때문에 쪼갤 필요가 없다.
로그인해야 코드를 작성할 수 있어요.