백준 20444번 | 색종이와 가위 (C++ 풀이)

 

 

  문제  

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

20444번: 색종이와 가위

---

  풀이  

• 사용 알고리즘 : 파라메트릭 서치
• 시간 복잡도 : $O(log N)$

파라메트릭을 활용한 재밌는 문제였습니다.

 

문제는 굉장히 단순합니다. 색종이를 $N$번 잘랐을 때, $K$개의 색종이를 만들어낼 수 있는가? 를 구하면 되죠.

 

먼저 생각해 볼 만한 점은, 색종이를 잘랐을 때 몇 개의 색종이가 더 생겨나는지를 일반화시킬 수 있을까? 입니다.

 

이는 그림을 조금 그려보시면 아시겠지만, 가로로 $x$번, 세로로 $y$번 색종이를 자르면 $(x + 1) * (y + 1)$ 개의 색종이가 생겨납니다.

 

이제 저 식을 사용해서 문제를 풀어보겠습니다.

 

가로로 색종이를 자를 횟수를 $x$라고 하면, 세로 횟수는 $N - x$가 될 겁니다. 즉, $(x + 1) * (N - x + 1) = K$를 만족하는 $x$ 값을 찾아주면 이 문제를 풀 수 있습니다.

 

그렇다면 이제 $x$에 대해 파라메트릭 서치를 돌려주면 되겠는데, 가능한 $x$의 범위를 고려해 봐야겠죠.

 

범위를 알아보기 위해 $(x + 1) * (N - x + 1)$ 의 그래프를 간략하게 나타내보면, 아래와 같습니다.

 

N = 2 일때

$n \over 2$ 일 때 최댓값을 가지는 이차함수이기 때문에, $0 \le x \le $ $n \over 2$ 범위 안에서는 단조 증가합니다. 따라서 파라메트릭을 돌릴 $x$의 범위는 $0 \le x \le $ $n \over 2$ 가 되겠죠.

 

만약 $(x + 1) * (N - x + 1)$ 의 값이 $K$보다 작다면 $x$의 값을 올리면 되고, $(x + 1) * (N - x + 1)$ 의 값이 $K$보다 크다면 $x$의 값을 낮추면 됩니다.

 

이렇게 $x$에 대한 이분 탐색을 하다가, $(x + 1) * (N - x + 1) = K$를 만족하는 $x$가 찾아진다면, 이는 색종이를 $N$번 잘랐을 때 $K$개의 색종이를 만들어낼 수 있다는 뜻이 되겠죠. 만약 $x$를 찾을 수 없다면, 이는 색종이를 $N$번 잘랐을 때 $K$개의 색종이를 만들어낼 수 없다는 뜻이 될 겁니다.

---

  코드  

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF = 1e18;
const int inf = 2e9;
const int SIZE = 1 << 18;
const int MOD = 1e9 + 7;

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	ll n, k;
	cin >> n >> k;
	ll lo = 0;
	ll hi = n / 2;
	ll mid;
	bool ans = false;
	while (lo <= hi) {
		mid = (lo + hi) >> 1; // mid 는 점차 중앙값에 근접해가기
		ll cnt = (mid + 1) * (n - mid + 1);
		if (cnt == k) {
			ans = true;
			break;
		}
		// 만약 값이 k보다 크다면 mid 값 낮추기
		else if (cnt > k) hi = mid - 1;
		// 만약 값이 k보다 작다면 mid 값 올리기
		else lo = mid + 1;
	}
	if (ans) cout << "YES";
	else cout << "NO";
	return 0;
}