[BOJ/C++] 20444: 색종이와 가위

🏅 Gold 5

✏️ 1차 솔루션

1. left = 1, right = n + 1 으로 시작
2. left * right 이 k 보다 작으면 색종이 조각을 더 늘려주기 위해 left += 1, right -= 1 로 갱신
3. left 와 right 가 같아질 때까지 k 조각이 되는 경우 찾기

🚨 1차 trouble

시간초과..이분탐색으로 안 풀어서 그런듯

✏️ 최종 솔루션

⭐️ 이분 탐색 풀이
기존 풀이에서 left, right 를 1 씩 이동해주면서 조절해주는 과정을 이분탐색으로 변환해주기

1. 반복할 때마다 mid 값 갱신
2. 가로로 mid 회 자르면 세로로 n - mid 회 잘라야 하기 때문에 반복마다 색종이 조각의 개수 = (mid + 1) * (n - mid + 1)
3. k 보다 개수가 작으면 색종이 조각을 늘리기 위해 left = mid + 1 로 mid 보다 큰 값으로 탐색 범위 이동
4. k 보다 개수가 크면 색종이 조각을 줄이기 위해 right = mid - 1 으로 mid 보다 작은 값으로 탐색 범위 이동

📌 self feedback

이분 탐색 적용을 끌어내는 게 너무 어렵다..유형마다 천차만별이라서 연습이 더 필요할듯..

✏️ 최종 code

#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;
    
}