44. 마구간 정하기

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

입력예제 1

53

1
2
8

4

9

 

출력예제 1 

3

 

풀이 

- 이분탐색 응용

- 마구간 개수 n의 범위가 광범위하므로, 동적할당 해준다 > 프로그램 종료 전 delete

- 마구간 좌표는 수직이고, 그 사이 거리들에 대한 정보가 필요함 > 정렬 필요, sort함수 사용

- mid: 이분탐색 시 키 값, 3마리의 말을 수용할 수 있을 시에 res값을 mid값으로 설정

 

이분탐색 시 상황

(1) 해당 mid값이 3마리의 말 수용 가능할 때

> 3마리의 말을 수용할 수 있는 mid보다 큰 수는 당연히 3마리의 말을 수용할 수 있음

> 문제에서 물어보는 값이 "최대거리"이기 때문에 lt=mid+1로 옮겨서 최대거리를 찾는다.

 

(2) 해당 mid값이 3마리의 말 수용 불가능할 때

> mid보다 작은 거리에 정답이 있다는 것

> rt=mid-1으로 옮겨서 찾는다.

 

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int n;

// 44. 마구간 정하기(결정 알고리즘)

int Count(int len, int x[]){
    int i, pos=x[1], cnt=1;
    for(i=2;i<=n;i++){
        if(x[i]-pos>=len){
            cnt++;
            pos=x[i];
        }
    }
    return cnt;
}

int main() {
    int m, i, lt=1, rt, mid,res;
    scanf("%d %d", &n, &m); //n: 마구간 좌표, m: 말 마리 수
    int *x = new int[n+1]; //n 범위가 큼 => 동적할당
    
    for(i=1;i<=n;i++){
        scanf("%d",&x[i]);
    }
    sort(x+1,x+n+1); //배열 정렬
    rt=x[n]; //가장 큰 좌표를 rt
    
    //이분탐색
    while(lt<=rt){
        mid=(lt+rt)/2;
        if(Count(mid,x)>=m){
            res=mid;
            lt=mid+1;
        }
        else rt=mid-1;
    }
    printf("%d\n", res);
    delete[] x; //배열 할당 해제
    return 0;
}