[백준] 12945 재미있는 박스 정리

 

생각하며 풀어야하는 문제다!

이런 쉽게쉽게 생각하고 최적을 찾는 문제 잘푸는 사람들이 있던데..

나는 아니다 ㅎㅎ

 

처음에 거꾸로 정렬시키고 투포인터로 뒤에서부터 보면 무조건 된다고 생각했다

근데 대충 테케를 만들어보다가

2 4 5 6 7 8 8 9 50 100 이걸 넣었다가 내 코드에서는 7이 나오는걸 발견했다 답은 6..!

 

생각해보면 최대답은 2/N이다 박스에 한개만 넣을수 있기 때문에!

 

그럼 우리는 반으로 잘라서 0~2/N, N/2+1~N 까지 l,r로 나눠서 넣어보면 된다!

 

풀고나면 참 쉬워보이는 문제.. 근데 한번에 떠올리기가 참 쉽지않다! 

 

소스코드

#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);
}