※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※
이번에 볼 문제는 백준 21507번 문제인 POBEDA-2014이다.
문제는 아래 링크를 확인하자.
https://www.acmicpc.net/problem/21507
1번과 2번을 하나씩 조합해 단위 사각형을, 3번과 4번을 하나씩 조합해 단위 사각형을 각각 하나씩 만들 수 있다.
문제에서 요구하는 정사각형은 위의 단위 사각형을 기준으로 만들 수밖에 없으므로, 위와 같이 만들 수 있는 단위 사각형들의 전체 넓이보다 작거나 같은 넓이를 가진 정사각형 중 한 변의 길이가 양의 정수인 가장 큰 정사각형의 변의 길이를 출력해 문제를 해결하자.
이러한 제곱근은 이진탐색을 통해 빠르게 구해낼 수 있다.
아래는 제출한 소스코드이다.
#include <iostream>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
ll a, b, c, d; cin >> a >> b >> c >> d;
ll sq = min(a, b) + min(c, d);
ll L = 0, R = 2000000000LL;
while (L < R) {
ll mid = (L + R) / 2 + 1;
if (mid * mid <= sq) L = mid;
else R = mid - 1;
}
cout << L;
}
728x90
'BOJ' 카테고리의 다른 글
[BOJ 2712 // C++] 미국 스타일 (0) | 2022.11.22 |
---|---|
[BOJ 20492 // C++] 세금 (0) | 2022.11.22 |
[BOJ 15488 // C++] 나이트가 체스판을 벗어나지 않을 확률 (0) | 2022.11.22 |
[BOJ 11434 // C++] Ampelmännchen (0) | 2022.11.22 |
[BOJ 26040 // C++] 특정 대문자를 소문자로 바꾸기 (0) | 2022.11.21 |