그래도 수명이 절반이 되어서는 풀이 및 코드

삼성 아카데미 문제이다. 

이게 이진 탐색 문제였다는것이 충격이였고 좋은 문제해결 전략을 취득한 느낌이다.

 

풀이는 간략하게

1. 수열을 읽으며 가장 높은 수(이분 탐색의 right), 가장 낮은 수(이분 탐색의 left)를 구한다.

2. 위 두 수 사이를 이분 탐색하여 답이 될 수 있는 후보 숫자하나를 가정한다.  

3. 그 숫자를 검증한다. 그 숫자가 유효하면 그 숫자를 이분 탐색의 left로 설정하고 left와 right가 같아질 때까지 2,3를 반복한다.

다음은 그 코드이다.

#include<stdio.h>
 
int mem[200001];
int piece[200001];
int N=0, K=0;
int sumofK=0;
 
bool check(int val){
 
    int cur =0;
    for(register int i =0;i<K;i++){
        if(sumofK>N-cur){
            return false;
        }
        int det =0;
        while(det==0){
            det =1;
            for(register int j =0;j<piece[i];j++){
                if(cur>=N)
                    return false;
                if(mem[cur]>val)
                {
                    det = 0;
                    cur++;
                    break;
                }
                cur++;
            }
            
        }
        sumofK-=piece[i];
    }
    
    return true;
}
int main(int argc, const char * argv[]) {
    // insert code here...
    int T =0;
    scanf("%d",&T);
    for(int test = 1; test<=T;test++){
        scanf(" %d %d",&N, &K);
        int left= 200001;
        int right =0;
        for(register int i =0; i<N;i++){
            scanf(" %d", &mem[i]);
          //  printf("left : %d, right : %d\n",left, right );
            if(mem[i]>right) right = mem[i];
            if(mem[i]<left) left = mem[i];
        }
        sumofK=0;
        for(register int i =0; i<K;i++){
            scanf(" %d", &piece[i]);
            sumofK+=piece[i];
        }
        printf("#%d ", test);
        int cur = (right+left)/2;
       // printf("left : %d, right : %d\n",left, right );
 
        while(left< right){
           // printf("left : %d, right : %d\n",left, right );
            int temp = sumofK;
            if(check(cur)){
                right = cur;
                
            }
            else{
                left = cur+1;
            }
            cur = (right+left)/2;
            sumofK = temp;
        }
        printf("%d\n", cur);
        
    }
    return 0;
}