알고리즘/BOJ
[백준] 12945 재미있는 박스 정리
세진짱
2020. 2. 5. 22:13
생각하며 풀어야하는 문제다!
이런 쉽게쉽게 생각하고 최적을 찾는 문제 잘푸는 사람들이 있던데..
나는 아니다 ㅎㅎ
처음에 거꾸로 정렬시키고 투포인터로 뒤에서부터 보면 무조건 된다고 생각했다
근데 대충 테케를 만들어보다가
2 4 5 6 7 8 8 9 50 100 이걸 넣었다가 내 코드에서는 7이 나오는걸 발견했다 답은 6..!
생각해보면 최대답은 2/N이다 박스에 한개만 넣을수 있기 때문에!
그럼 우리는 반으로 잘라서 0~2/N, N/2+1~N 까지 l,r로 나눠서 넣어보면 된다!
풀고나면 참 쉬워보이는 문제.. 근데 한번에 떠올리기가 참 쉽지않다!
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include <iostream>
#include <algorithm>
using namespace std;
int n,ans;
int arr[500050];
int main(){
scanf(" %d",&n);
for(int i=0;i<n;i++) scanf(" %d",&arr[i]);
sort(arr,arr+n);
int l=0,r=n/2;
while(l<n/2 && r<n){
if(arr[l]*2<=arr[r]){
ans+=1;
l+=1;
}
r+=1;
}
printf("%d\n",n-ans);
}
|