boj 1654 랜선 자르기 문제를 (st+en)/2 형태로 작성할 수 있는 방법에 대한 참고 블로그.

우선적으로 내가 접한 코드의 경우는 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int k, n;
int arr[10005];

bool solve(ll x){
  ll cur = 0;
  for(int i = 0; i < k; i++) cur += arr[i] / x;
  return cur >= n;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> k >> n;
  for(int i = 0; i < k; i++) cin >> arr[i];
  ll st = 1;
  ll en = 0x7fffffff; // 2^31 - 1
  while(st < en){
    ll mid = (st+en+1)/2;
    if(solve(mid)) st = mid;
    else en = mid-1;
  }
  cout << st;
}

이런 형태로 작성되있는 코드이다. 

이 경우 이 코드를 while 문의 판단 부분을 st<=en 으로 작성한다거나, ll mid=(st+en)/2; 으로 작성한다거나, 

st=mid+1; 로 작성한다거나 하면 정상적으로 답을 출력하지 못한다. 무한 루프에 빠진다거나, 혹은 출력값이 잘못되어서 200이 출력되어야 할것을 201을 출력한다거나 하는 형태이다. 

 

이와 관련하여서 문제에 대해서 검색하였을때 발견한 코드를 참고해보면, 아래 블로그에 작성하신 분의 풀이와 코드를 참고할 수 있다.

https://yongmemo.tistory.com/21

[BOJ 1654] 랜선 자르기 C++ 풀이 // 이분 탐색(이진 탐색) 설명

 

이 때 이 코드를 참고해서 내가 작성해본 코드를 덧붙이자면, 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int k, n;
int arr[10005];
ll ans=0;

bool solve(ll x){
  ll cur = 0;
  for(int i = 0; i < k; i++) cur += arr[i] / x;
  return cur >= n;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> k >> n;
  for(int i = 0; i < k; i++) cin >> arr[i];
  ll st = 1;
  ll en = 0x7fffffff; // 2^31 - 1
  while(st <= en){
    ll mid = (st+en)/2;
    if(solve(mid)){
        st = mid+1;
        ans=max(ans,mid);
    } 
    else en = mid-1;
  }
  cout << ans;
}

이러한 형태로 코드를 작성하였고, 

이때에 

ll ans;

ans=max(ans, mid); 형태로 ans 변수를 두고 이 변수를 계속 큰 값으로 최신화 하면서

그 ans를 출력하는 방식을 통해서 st<=en 으로 두기, ll mid=(st+en)/2 로 두기, st=mid+1로 두기 등으로 코드를 작성할 수 있었다. 

물론 st<en 으로 두기, mid=(st+en+1)/2; st=mid 형태로 두어서 마지막에 st를 출력하는것을 이해하고 그렇게 작성해도 되지만, 

현재는 두번째 제시한 형태의 코드로 문제를 푸는것이 더욱 마음에 들어서 이러한 방법을 기록하고 다음에도 이러한 방법을 이용해서 문제를 풀어보려 한다. 

 

일단 두가지 방법 모두에 대해서 이해하고 자유자재로 사용할 수 있도록 노력해보도록 하자. 

 

결국 parametric search 문제의 경우는 stl 함수를 활용하는 식으로 문제를 해결할 수 없으니 이렇게 직접적으로 이분탐색을 코드로 구현해서 문제를 풀어야 하는데, 이때에 확실하게 방법들을 이해하고 자유자재로 작성해서 문제를 해결할 수 있도록 해보자.