※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 21507번 문제인 POBEDA-2014이다.
문제는 아래 링크를 확인하자.

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

 

21507번: POBEDA-2014

Первая строка входного файла содержит разделенные пробелами четыре целых числа: a1, a2, a3, a4 (0 ≤ a1, a2, a3, a4 ≤ 1018). Входные данные могут превышать

www.acmicpc.net

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

+ Recent posts