boj 16401번 문제를 풀며 접하게된 *max_element(l,l+n);의 활용.

일단 내 풀이의 경우는 

    int st=1;
    int en=1'000'000'000;

처음 시작값과 끝값을 이런식으로 설정해서 이분탐색을 시작한다. 이 경우는 결국에 과자의 최대길이부터 끝값으로 잡고 문제를 돌리는것이 어느정도의 연산 횟수를 줄일 수 있는 방법은 맞을것이지만, 결국 이분탐색을 통해서 굉장히 빠르게 그 값에 근접하는 부분까지 값이 떨어져 내려갈것이다. 그리고 이번에 접한 풀이 코드에서, 

  int st = 0;
  int en = *max_element(l, l+n);

이런식으로 int en=*max_element(l,l+n); 형태로 작성하는 것을 보게되었다. 

그 전에는 배열에 입력값을 받을때마다 max() 함수를 이용해서 계속해서 en이 될 값을 갱신해주는 코드를 보았는데, 

그렇게 하는것보단 이런식으로 *max_element()를 활용하는 형태의 코드가 더욱 마음에 든다.

 이 풀이의 경우는 한번 나중에 이런식의 parametric search 문제를 접했을때 en의 값을 잡을때 최대로 값의 범위의 끝을 쓰는것보다

이런식으로 주어지는 원소의 최대값을 *max_element() 를 이용해서 사용해봐도 좋을것 같다.

 우선적으로 이 방법을 알아두고 다음에 한번 사용해보면서 익숙해져 보도록 하자. 

그리고 이번에 접한 풀이의 경우도 

  while (st < en) {
    int mid = (st + en + 1) / 2;
    if (solve(mid))
      st = mid;
    else
      en = mid - 1;
  }
  cout << st << "\n";

이렇게 while문을 계속 돌려서 마지막에 st를 출력하는 형태의 코드이고, 이런 코드를 작성할때는

while(st<en) 으로 놓는다는것, 

mid=(st+en+1)/2; 로 놓는다는것, 

그리고 st=mid; 로 갱신해준다는것, 

이런 과정을 모두 거치고 나서 st를 출력한다는걸 이해하고 사용하도록 하자. 

 

내가 이번 문제를 풀때 사용한 방법은 (st+en)/2로 두고싶고, st=mid+1; en=mid-1; 로 두고 싶어서, 

    while(st<=en){
        int mid=(st+en)/2;
        if(solve(mid)) {
            ans=max(ans,mid);
            st=mid+1;
        }else 
            en=mid-1;
    }
    cout<<ans;

이런식으로 코드를 작성해서 문제를 해결하였다.

기본적으로 나는 아래로 작성한 코드가 더욱 마음에 들어서 앞으로 이런 형태의 문제들을 만나게 되면 지속적으로 아래와 같은 형태로 문제를 해결하겠지만, 위와 같은 형태도 충분히 이해해놓고 자유자재로 사용할 수 있도록 만들어두자. 

 

+++++++++

참고로 en=1'000'000'000; 을 이용하는 것과 en=*max_element(a,a+n);을 이용하는 것의 제출했을시의 차이점은, 

8ms차이가 난다. 시간적으로 그렇게 많은 차이를 보이는 형태는 아니기 때문에 어느 형태를 사용하든 큰 차이를 만들지는 않을것 같다. 

하지만 *max_element(a,a+n); 형태의 코드가 꽤나 마음에 든다.