🖊️ 문제

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

---

🖊️ 풀이

일단,

이렇게 자른다.

일단 생각해보면,
n번 가위질 : k개 조각 이라고 치면,
1 : 2
2 : 3 / 4
3 : 4 / 6
4 : 5 / 8 / 9
5 : 6 / 10 / 12
6 : 7 / 12 / 15 / 16

무슨 연관이 있을까? 생각해봤는데,
자르는 알고리즘을 생각해보니 답이 나왔다.

가로로 a번, 세로로 b번 자른다고 치면
자른 조각은 (a + 1) * (b + 1)개가 된다.

n번 자른다고 주어졌으니, b = n - a이 된다.
다시 식을 수정하면
(a+1) * (n-a+1) 개의 조각이 나올 수 있다.
a는 0 ~ n/2가 되겠다.

근데 숫자 범위가 너무 컸다.
(1 ≤ n ≤ 231-1, 1 ≤ k ≤ 263-1)

그래서 이분탐색인가? 싶었다.

#include <iostream>
using namespace std;

typedef unsigned long long ull;

int main()
{
	ull n, k;
	cin >> n >> k;

	string result = "NO";
	
	ull left = 0;
	ull right = n / 2;
	ull leftValue = (left + 1) * (n - left + 1);
	ull rightValue = (right + 1) * (n - right + 1);
	ull mid = (leftValue + rightValue) / 2;

	while (left < right) {
		if (leftValue == k || rightValue == k) {
			result = "YES";
			break;
		}
		else if ((leftValue + rightValue) / 2 < k) {
			left++;
			leftValue = (left + 1) * (n - left + 1);
			}
		else {
			right--;
			rightValue = (right + 1) * (n - right + 1);
		}
	}

	cout << result;
}

그치만 시간제한은 0.1초였고...
너무 택도없었다.

근데 스카 시간이 끝나서 다음날 풀었다.

그리고 다음날 다시 보니..
저건 진짜 비효율적인 이분탐색이었다...
그냥 투포인터?라고 봐야하나

다시 생각하고 구현했다.

#include <iostream>
using namespace std;

typedef long long ll;

int main()
{
	ll n, k;
	cin >> n >> k;

	string result = "NO";

	ll left = 0;
	ll right = n/2;
	ll mid = 0;
	ll midValue = 0;
	
	while (left <= right) {
		mid = (left + right) / 2;
		midValue = (mid + 1) * (n - mid + 1);
		if (midValue > k) right = mid - 1;
		else if (midValue < k) left = mid + 1;
		else {
			result = "YES";
			break;
		}
	}

	cout << result;
}

근데 여기서!!
계속 시간초과가 났다.

혹시나 했더니,
unsigned long long으로 선언했던 부분을 long long으로 변경했더니 시간초과가 해결됐다.

이건 구글링을 통해 이유를 알아냈다.

unsigned long long은 음수를 저장할 수 없기 떄문에, 음수가 저장되면 오버플로우가 일어난다.

https://www.acmicpc.net/board/view/120690

흠.. 좀만 더 생각하고 풀길!