[백준] 20444번 : 색종이와 가위 (C++)

20444번 : 색종이와 가위

---

문제)

오늘도 역시 준성이는 어김없이 색종이와 쿼리를 푸는 데 실패하였다!!

색종이에 열등감을 느낀 준성이는 가위로 눈에 보이는 색종이를 모두 잘라 버리려고 한다!!

색종이를 자를 때는 다음과 같은 규칙을 따른다.

색종이는 직사각형이며, 색종이를 자를 때는 한 변에 평행하게 자른다.
자르기 시작했으면, 경로 상의 모든 색종이를 자를 때까지 멈추지 않는다.
이미 자른 곳을 또 자를 수 없다.

 

분노에 찬 가위질을 하던 준성이는 갑자기 하나의 색종이를 정확히 n번의 가위질로 k개의 색종이 조각으로 만들 수 있는지 궁금해졌다.
궁금하지만 화가 나서 코딩에 집중할 수 없는 준성이 대신 코드를 작성해주도록 하자.

 

 

입력 :

첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 2^31-1, 1 ≤ k ≤ 2^63-1)

 

 

 

출력 :

첫 줄에 정확히 n번의 가위질로 k개의 색종이 조각을 만들 수 있다면 YES, 아니라면 NO를 출력한다.

 

 

 

 

풀이)

 

// 20444. 색종이와 가위
#include <iostream>
 
using namespace std;
 
long long n, k;
 
// 가로로 자른 횟수 a, 세로로 자른 횟수를 b라고 하면
// n = a + b;
 
// 색종이의 총 개수는
// (a + 1)(b + 1) = k가 된다.
 
// 이를 입력값과, 한 횟수에 대해서 정리하면
// (a + 1)(n - a + 1) = k 가 되고.
// n, k가 주어져있기 때문에 
// a에 대해 이분탐색을 진행하면 답이 나오게 된다.
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> k;
 
    long long s = 0;
    long long e = n;
 
    while (s <= e)
    {
        long long mid = (s + e) / 2;
        long long ans = (mid + 1) * (n - mid + 1);
 
        if (ans == k)
        {
            cout << "YES";
            return 0;
        }
        else
        {
            if (s == e) break;
            if (ans > k) e = mid - 1;
            else s = mid + 1;
        }
    }
 
    cout << "NO";
 
    return 0;
}
 

---

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

20444번: 색종이와 가위