[Inflearn] 마구간 정하기(binary search apply)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 이 문제도 답의 구간을 이분하면서 최적의 결정하는 알고리즘이다

     

     5 3

     1 2 8 4 9 가 입력되었을 때,

     좌표 계산이 필요하므로 입력된 값들을 정렬해준다.

     1 2 4 8 9

     여기서 두 말의 최대 거리는 1 ~ 9 사이에 있을 것이다. 

     그렇다면 답의 구간을 이분하면서 최적의 답을 찾아보자.

     먼저 lt = 1, rt = 9

     mid = (rt - lt) / 2 = 5

     정렬된 숫자들을 탐색하면서 가까운 두 말의 최대 거리인 5라고 했으니까,

     두 말의 거리가 5 이상인 말이 총 몇 마리가 있는지 count 해보자.

     1 2 4 8 9 에서

     cnt = 1  (1번 마구간에 말이 있으므로)

     1, 2 의거리는 1 이므로 pass

     1, 4 의 거리는 2 이므로 pass

     1, 8 의 거리는 7 이므로 cnt++

     8, 9 의 거리는 1 이므로 pass

     세 마리의 말이 마구간에 들어가야 하는데 1번, 8번 마구간, 두 마리의 말 밖에 할당이 안 되었다.

     그러므로 정답은 1 ~ 4 사이에 있을 것이다.

      rt = 4

      mid = (rt - lt) / 2 = 2

      두 말의 거리가 2 이상인 말이 총 몇 마리가 있는지 count 해보자.

      1 2 4 8 9 에서

      cnt = 1

      1, 4 의 거리는 3 이므로 cnt++

      4, 8 의 거리는 4 이므로 cnt++

      세 마리의 말이 마구간에 모두 들어있다.

      rst = 2

      그러면 정답의 범위는 3 ~ 4 사이에 있을 것이다.

     lt = 3

     mid = (rt - lt) / 2 = 3

     두 말의 거리가 3 이상인 말이 총 몇 마리가 있는지 count 해보자.

     1 2 4 8 9 에서

     cnt = 1

     1, 4 의 거리는 3 이므로 cnt++

     4, 8 의 거리는 4 이므로 cnt++

     세 마리의 말이 마구간에 모두 들어있다.

     rst = 3

     마지막으로 4만 확인해보면 된다.

     lt = 4

     ..

#. Code

#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    freopen("input.txt", "rt", stdin);
 
    int n, c, i, lt = 1, rt, mid, cnt, pos, dist, rst = -2147000000;
 
    scanf("%d %d", &n, &c);
    vector<int> vt(n + 1);
    for (i = 1; i <= n; i++)
        scanf("%d", &vt[i]);
    
    sort(vt.begin(), vt.end());
 
    rt = *(vt.end()-1);
 
    while (lt <= rt)
    {
        cnt = 1;
        pos = 1;
        dist = 0;
 
        mid = (lt + rt) / 2;
        
        while (pos < n)
        {
            for (i = pos; i < n; i++)
            {
                if (vt[i + 1] - vt[pos] >= mid)
                {
                    cnt++;
                    pos = i + 1;
                    break;
                }
            }
 
            if (i == n)
                break;
        }
 
        if (cnt >= c)
        {
            rst = rst < mid ? mid : rst;
            lt = mid + 1;
        }
        else
            rt = mid - 1;
    }
 
    printf("%d\n", rst);
 
    return 0;
}

로직대로 하긴 했다만 뭔가 지저분한 느낌이다ㅠㅠ

일단 rst 를 min 값으로 두고 비교해서 저장할 필요가 없었다.

그냥 mid 값을 바로 저장해줬으면 됐는데.. 윽..

dist 변수도 필요 없고, line 48에 rst = mid 로 해줘도 무관하다

왜이렇게 복잡하게 주먹구구식으로 짯지?ㅋㅋㅋㅋ

while (pos < n)
{
    for (i = pos; i < n; i++)
    {
        if (vt[i + 1] - vt[pos] >= mid)
        {
            cnt++;
            pos = i + 1;
            break;
        }
    }
        if (i == n)
        break;
}
 
// 수정 후
 
for (i = 2; i <= n; i++)
{
    if (vt[i] - vt[pos] >= mid)
    {
        cnt++;
        pos = i;
    }
}

pos의 위치는 고정이고 i값만 변하니까 특정 상황에서만 pos을 변경시켜주면 될텐데

디버깅하면서 뜯어고치다보니까 주먹구구식이 되었던 것 같다.

집중하자 집중!!

#. Other code

#include<stdio.h>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int n;
 
int Count(int len, int x[]){
    int i, cnt=1, pos=x[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);
    int *x = new int[n+1];
 
    for(i=1; i<=n; i++)
        scanf("%d", &x[i]);
    
 
    sort(x+1, x+n+1);
    rt=x[n];
 
    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;
}

이전 문제와 거의(?) 유사한 로직이다.

강사님의 코드는 정말 깰끔, 간결하다.

본받자..

#. Result

  - Input --------------------------------------------------------

5 3

1

2

8

4

9

------------------------------------------------------------------

  - Output --------------------------------------------------------

3

------------------------------------------------------------------