[20444] 색종이와 가위

20444번: 색종이와 가위

수학적 접근이 필요한 이분 탐색 문제다.

 

색종이를 n번 잘랐을 때 k개가 되는지 여부를 확인하는 문제. 가로로 잘린 횟수 + 1와 세로로 잘린 횟수 + 1의 곱이 잘린 색종이의 개수가 되는데, 이때 가로로 잘린 횟수를 x라 두면, 세로로 잘린 횟수는 n - x가 되므로 둘의 곱은 이차 방정식으로 나타낼 수 있다. 여기서 y = k와의 해가 있는지 확인하기 위해 그래프로 확인할 필요가 있다는 점에서 수학적 접근이 필요하다.

 

모눈선의 숫자는 무시하자 ^,,^

 

위 그래프는 잘린 종이의 개수 y = (x + 1) * (n - x + 1) 에 대한 그림이다.

보다시피 x = -1, n + 1이며, 우리는 y = k와의 해를 구하기 위해 위 그래프에 y = k를 임의로 그려볼 수 있을 것이다. 물론 y = k였을 때 두 방정식의 연립방정식을 구할 수 있겠지만, 완전히 수학적으로 풀기 보다 x의 범위를 이분 탐색으로 줄여나가며 y`이 k가 될 수 있을지 여부만 판단하기로 하자.

 

보다시피 x는 값이 두 개라 범위를 어떻게 좁혀야할지 고민이 될 수 있겠지만 문제에서는 단순히 k가 될 수 있는지만 확인하면 되므로 x의 정확한 값은 중요하지 않다. 대칭구조이므로 중앙점인 n/2까지만 확인하며 범위를 줄여도 무관하다.

 

#include <iostream>
#include <string>

using namespace std;
typedef long long ll;
int main()
{
    int n; 
    ll k;
    
    cin >> n >> k;
    
    ll start = 0;
    ll end = n / 2;
    
    string flag = "NO";
    
    while(start <= end){
        ll middle = (start + end) / 2;
        
        ll peices = (middle + 1) * (n - middle + 1);
        
        if(peices == k){
            flag = "YES";
            break;
        }
        
        if(peices > k) end = middle - 1;
        else start = middle + 1;
    }
    
    cout << flag; 

    return 0;
}