YEJIN LEE

“Keep turnin’ the pages”

2 minute read

이분 탐색 Binary Search

문제

오늘도 역시 준성이는 어김없이 색종이와 쿼리를 푸는 데 실패하였다!!

색종이에 열등감을 느낀 준성이는 가위로 눈에 보이는 색종이를 모두 잘라 버리려고 한다!!

색종이를 자를 때는 다음과 같은 규칙을 따른다.

  • 색종이는 직사각형이며, 색종이를 자를 때는 한 변에 평행하게 자른다.
  • 자르기 시작했으면, 경로 상의 모든 색종이를 자를 때까지 멈추지 않는다.
  • 이미 자른 곳을 또 자를 수 없다.
    분노에 찬 가위질을 하던 준성이는 갑자기 하나의 색종이를 정확히 n번의 가위질로 k개의 색종이 조각으로 만들 수 있는지 궁금해졌다.
    궁금하지만 화가 나서 코딩에 집중할 수 없는 준성이 대신 코드를 작성해주도록 하자.

입력

첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 2^31-1, 1 ≤ k ≤ 2^63-1)

출력

첫 줄에 정확히 n번의 가위질로 k개의 색종이 조각을 만들 수 있다면 YES, 아니라면 NO를 출력한다.

예제 입력 1 
4 9

예제 출력 1 
YES

🪨풀이

이 문제는 이분탐색과 매개변수탐색을 이용하여 풀 수 있다.

n 번의 가위질로 k개의 조각을 만들어야 하는데, 이를 어떻게 일반화 시킬까 고민해보아야 한다.
가로로 x번 세로로 y번 자른다고 했을때, K = (x + 1)*(y + 1)이 된다.
이 때, N = x + y이므로 K = (x + 1)*(N - x + 1)이다.

여기서 위의 식을 만족시키는 x를 구하면 된다. 구하려는 x를 매개변수탐색에서 공부했듯이 mid로 놓고 x의 범위를 low, high로 잡아 이분 탐색을 진행하면 된다. 결정함수는 조건문으로 K = (x + 1)*(N - x + 1)를 만족하는지 검사하는 기능을 넣어주면 된다.

위의 방정식을 풀어봤을 때 x가 2/n에서 최대값을 가지는 이차함수 형태이므로, x의 범위는 0부터 2/n까지가 된다. 따라서 low = 0, high = 2/n으로 초기값을 잡고 시작한다. 탐색하는 x는 이분탐색에서와 같이 low와 high의 중간값이 되고, (x + 1)*(N - x + 1)의 값이 입력받은 k와 같다면 YES를 출력후 리턴하고, 끝까지 찾지 못한다면 NO를 출력한다.

💻코드

/*
* [백준 20444] 색종이와 종이
* 오늘도 역시 준성이는 어김없이 색종이와 쿼리를 푸는 데 실패하였다!!
* 색종이에 열등감을 느낀 준성이는 가위로 눈에 보이는 색종이를 모두 잘라 버리려고 한다!!

* 종이를 자를 때는 다음과 같은 규칙을 따른다.
	* 색종이는 직사각형이며, 색종이를 자를 때는 한 변에 평행하게 자른다.
	* 자르기 시작했으면, 경로 상의 모든 색종이를 자를 때까지 멈추지 않는다.
	* 이미 자른 곳을 또 자를 수 없다.

*분노에 찬 가위질을 하던 준성이는 갑자기 하나의 색종이를 정확히 n번의 가위질로 k개의 색종이 조각으로 만들 수 있는지 궁금해졌다.
* 궁금하지만 화가 나서 코딩에 집중할 수 없는 준성이 대신 코드를 작성해주도록 하자.
*
* [알고리즘]
* 이분 탐색/ 매개 변수 탐색
* 32비트 = 4바이트 = int
* 64bit = 8byte = long long
* 
* 
*/

#include<iostream>
#include<algorithm>
#include<vector>	

using namespace std;

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

	long long n, k, mid;
	cin >> n >> k;
	long long low = 0; long long high = n / 2;

	while (low <= high) {
		mid = (low + high) / 2;
		long long tmp = (mid + 1) * (n - mid + 1);
		if (tmp == k) {
			cout << "YES"; return 0;
		}
		else if (tmp > k) high = mid - 1;
		else low = mid + 1;
	}
	cout << "NO";

	return 0;
}

You may also enjoy