[Algo] 백준 랜선자르기 c++ // 매개변수 탐색, 무한루프 확인법

• 이 문제는 2회차푸는 문제다.
• x길이의 고정된길이로 막대를 자른다는 제약조건이 있다. (파악하기 힘들었음)

 

* 매개변수 탐색 학습, 의사코드

• 매개변수 탐색은 이분탐색의 응용편이다.
• f(x)를 정의하라. // f(x) : 랜선의 길이가 x일때, 갯수가 11개 이상이 나오는지.
• 우선, f(1)과 f(끝)을 직접 구한다.
  • 랜선의 길이가 1일때, 갯수는 무조건 11개 이상이나온다.
  • 랜선의 길이가 max일때, 갯수는 무조건 1개이다.
• f(mid)가 참인경우
  • 같은숫자를 연결하면된다.
  • 즉, f(1) ~ f(mid)는 계산할필요없이 모두 1인것이다. 
  • 이경우, 우측으로 재귀적으로 재탐색하면 된다.
  • 이때, mid자체도 정답의 범위에( true이므로) 포함되기떄문에, st = mid로 둬야함에 주의

  • 

• f(mid)가 거짓인경우
  • 같은숫자를 연결하면된다.
  • 즉, f(mid)~f(max)는 계산할필요없이 모두 1인것이다. 
  • 이경우, 좌측으로 재귀적으로 재탐색하면 된다.
  •  

 

• 마지막으로 값이 1개가 남을때까지 진행하면, 그게 정답이다.

 

* go 함수 구현

• 길이가 x 일때, 막대기갯수가 11(k)개 이상 나오는지 리턴한다.
•  

ll go(ll x) {
    ll cnt = 0; //막대기갯수
    for (int i = 0; i < n; ++i) {
        cnt += arr[i] / x;
    }
    return cnt >= k;
}

 

* 전체코드

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

int ret;
int n, k;
int arr[10004];

ll go(ll x) {
    ll cnt = 0; //막대기갯수
    for (int i = 0; i < n; ++i) {
        cnt += arr[i] / x;
    }
    return cnt >= k;
}
int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    ll st = 0;
    ll en = pow(2,31) - 1;

    while (st < en) {
        ll mid = (st + en +1 ) / 2;

        if (go(mid)) {
            st = mid;
        }
        else {
            en = mid - 1;
        }
    }

    cout << st;

    return 0;
}

 

* 무한루프 확인법

• 1차이나는 2, 3으로 코드를 돌려보면 된다.
  • 2 3
  • mid = 5/2 = 2
  • lo=2
  • 2 3
  • mid = 5/2 = 2
  • 무한반복..
• 해결
  • lo+hi+1하면 된다.
  • 2 3
  • mid = 6/2=3
  • lo=3
  • lo<hi 불만족 -> 탈출
• 이처럼 다음 st, en에 따라 mid 계산시 +1 할지 안할지도 봐줘야 한다.

 

 

* 레퍼런스

https://www.youtube.com/watch?v=F6lKjRDlOpk