# 20444. 색종이와 가위

관련 알고리즘 : 이분 탐색

 

문제 링크 : https://www.acmicpc.net/problem/20444

20444번: 색종이와 가위

 

---

해결 과정

조건을 보면, 색종이는 변에 평행하게만 자를 수 있으므로, 가로 x번 / 세로 y번 자를 때 

잘린 조각의 수는 (x+1)(y+1) 이다.

 

문제에서 n번의 가위질로 k개의 색종이 조각을 만들어야 하므로, (x+1)(y+1) 을 이용해 식을 세워보면,

• x+y = n
• y = n - x
• (x+1)(y+1) = (x+1)(n-x+1) = k

를 만족하여야 한다.

 

해당 식을 만족하는 값 x가 존재해야 YES를 출력 가능하므로, 결국 다음 식의 해 x값이 존재하는지를 찾는 것이 문제 해결의 키라 할 수 있겠다.

주어진 범위 (1 ≤ n ≤ 2^31-1, 1 ≤ k ≤ 2^63-1) 이 크므로 탐색 시간을 줄일 수 있는 방법을 찾아야 하는데,

이분 탐색을 이용하면 O(logN)의 시간으로 탐색 가능하다.

 

(x+1)(n-x+1) = -x^2+nx+(n+1) = -(x-n/2)^2 + ~~ 이므로 x = n/2에 대해 대칭, 위로 볼록인 이차함수 형태가 된다.

y=k를 만족하는 양의 정수 x값이 존재하는가 여부에 따라 yes/no의 출력 형태가 결정되므로,

구간을 0~n/2로 나눠 이분 탐색을 실행하면 답을 구할 수 있다.

 

---

C++ 코드

 

// BOJ 20444. 색종이와 가위

#include <iostream>
#include <cmath>

using namespace std;

long long n, k;
int res;


int cut(long long n, long long k) //  이분탐색
{
	long long cuttings; // 잘린 색종이 조각 수
	long long start = 0;
	long long end = n/2;
	long long mid;

	while (start <= end)
	{
		mid = (start + end) / 2;

		cuttings = (mid + 1) * (n - mid + 1);

		if (cuttings > k) // 잘린 조각 수가 k보다 많을 때
		{
			end = mid - 1;
		}
		else if (cuttings < k) // 잘린 조각 수가 k보다 적을 때
		{
			start = mid + 1;
		}
		else // 잘린 조각 수 = k일 때
		{
			return 1; // true 반환
		}
	}
	return 2; // 해가 존재하지 않을 때 2(false) 반환

}

void print(int num)
{
	if (num == 1)
	{
		cout << "YES" << '\n';
	}
	else
	{
		cout << "NO" << '\n';
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> k;

	res = cut(n, k);
	print(res);
	return 0;
}