알고리즘, PS, 문제풀기등/2) 탐색 알고리즘(DFS, BFS, 이진 탐색)
숫자구슬(정올) / 백준 숫자구슬(2613) - 이분탐색
tonyhan18
2023. 2. 7. 23:14
728x90
숫자구슬
https://www.acmicpc.net/problem/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
https://www.acmicpc.net/problem/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
728x90