[BAEKJOON] 20444 색종이와 가위 (C++)

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

20444번: 색종이와 가위

이미지 다운로드해서 대표이미지 설정하기 귀찮아졌다.

문제

가위질을 N번하여 K개의 종이 조각으로 만들 수 있는지 확인하는 문제

 

 

문제를 풀기 위한 핵심적인 아이디어

1. 가위질을 가로로 하든 세로로 하든 순서는 상관없다. 각 방향으로 몇번을 하는지에 

따라 최종적인 종이조각의 개수가 결정된다.

 

2. 가로 세로 가위질 횟수의 차이가 적을수록 종이조각이 많이 발생한다. ex 총 가위질횟수가 4인 경우 가로 세로 각각 2번씩 할 때 종이조각이 가장 많다 -> 이부분에서 이분탐색 아이디어가 적용된다.

 

3. 종이조각의 개수 = (가로 방향 가위질+1) * (세로 방향 가위질 +1)

 

코드

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

#define endl "\n"

using namespace std;

long long  N, K, ans;

void Input() {
	cin >> N>>K;
}

void Solve() {
	long long l = 0, r = N, m, cnt;
	while (l <= r) {
		m = (l + r) / 2;
		cnt = (m + 1) * (N - m + 1);

		if (cnt == K) break;
		else if (cnt < K) r = m-1;
		else l = m + 1;
	}

	if (cnt == K) cout << "YES";
	else cout << "NO";
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "r", stdin);
	Input();
	Solve();


	return 0;
}