left = 1
, right = n + 1
으로 시작left * right
이 k 보다 작으면 색종이 조각을 더 늘려주기 위해 left += 1
, right -= 1
로 갱신시간초과..이분탐색으로 안 풀어서 그런듯
⭐️ 이분 탐색 풀이
기존 풀이에서 left, right 를 1 씩 이동해주면서 조절해주는 과정을 이분탐색으로 변환해주기
mid
회 자르면 세로로 n - mid
회 잘라야 하기 때문에 반복마다 색종이 조각의 개수 = (mid + 1) * (n - mid + 1)
left = mid + 1
로 mid 보다 큰 값으로 탐색 범위 이동right = mid - 1
으로 mid 보다 작은 값으로 탐색 범위 이동이분 탐색 적용을 끌어내는 게 너무 어렵다..유형마다 천차만별이라서 연습이 더 필요할듯..
#include <iostream>
#include <vector>
using namespace std;
int main() {
long long n,k;
cin >> n >> k;
long long left=0,right=n;
string ans="NO";
while(left<=right) {
long long mid=(left+right)/2;
long long value=(mid+1)*((n-mid)+1);
if(value>k) {
right=mid-1;
}
else if(value<k) {
left=mid+1;
}
else {
ans="YES";
break;
}
}
cout << ans << endl;
}