숫자구슬(정올) / 백준 숫자구슬(2613) - 이분탐색

숫자구슬

 

https://www.acmicpc.net/problem/2613

2613번: 숫자구슬

#include <iostream>
using namespace std;
 
int N, M;
int arr[300];
 
bool isPossible(int mid) {
    int sum = 0, groupCnt = 1;
    for (int i = 0; i < N; i++) {
        sum += arr[i];
        if (sum > mid){
            sum = arr[i];
            groupCnt++;
        }
    }
    return groupCnt <= M;
}
 
void printAns(int mid){
    cout << mid << '\n';
 
    int i, sum = 0, marbleCnt = 0;
    for (i=0; i < N; i++) {
        sum += arr[i];
        if (sum > mid) {
            sum = arr[i];
            M--;
            cout << marbleCnt << " ";
            marbleCnt = 0;
        }
        marbleCnt++;
        // M개의 그룹을 만들기 위해 최소한의 구슬은 남겨둡니다.
        // (나머지 그룹에 적어도 구슬 1개를 배치해야 하기 때문.)
        if (N - i == M) break;
    }
 
    // 위에서 구한 구슬 개수를 현재 그룹까지만 출력하고
    // 나머지 남은 그룹에는 구슬 1개씩 배치
    while (M--){
        cout << marbleCnt << " ";   
        marbleCnt = 1;
    }
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    int left = 0, right = 0, mid;
    for(int i=0; i<N; ++i){
        cin >> arr[i];
        // 원소 중 최대값으로 left 설정
        left = left < arr[i] ? arr[i] : left;
        right += arr[i];
    }
        
    while (left <= right) {
        mid = (left + right) / 2;
        if(isPossible(mid))
            right = mid - 1;
        else
            left = mid + 1;
    }
 
    // 정답 출력
    printAns(left);
}

 

 

 

제곱근

 

http://www.codepass.co.kr/bbs/bbs_solve_lecture.php?idx=167&prod_idx=523&pCode=lecture&seq=5&page=1 

문제

https://www.acmicpc.net/problem/13706

13706번: 제곱근

https://www.acmicpc.net/problem/2417

2417번: 정수 제곱근

#if 1
#include <iostream>
#define ll unsigned long long
using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	//freopen("input.txt", "r", stdin);

	ll N;
	cin >> N;

	ll s = 1;
	ll e = N;
	ll mid = 0;
	ll ans = 0;
	while (s <= e)
	{
		mid = (s + e) / 2;
		if (mid <= N / mid)
		{
			ans = mid;
			s = mid + 1;
		}
		else {
			e = mid - 1;
		}
	}
	cout << ans << '\n';
}
#endif

 

 

# 이분탐색
n = int(input())
low = 1
high = n

while 1:
    mid = (low + high) // 2
    if mid ** 2 == n:
        print(mid)
        break
    elif mid ** 2 > n:
        high = mid - 1
    elif mid ** 2 < n:
        low = mid + 1