백준 색종이와 가위(이분탐색)

문제

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

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

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

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

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

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

 

입력

첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 231-1, 1 ≤ k ≤ 263-1)

 

출력

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

 

접근 방법 

전체 자르는 횟수를 n번이라 할 때 n번 안에서 가로 a번, 세로 b번을 잘라 n = a+b가 된다. 따라서 총 잘린 종이의 개수는 (a+1)(b+1)=k이다. a를 0~n까지 시도하여 (a+1)(b+1)=k를 만족하는 a가 있는 지를 판단하면 된다. 다만 이 경우는 O(N)으로 시간을 초과하므로 이분탐색을 이용하여 O(logN)으로 풀 수 있다.

 

코드

n, k = map(int, input().split())

def find(L, R, k):

    if L > R:

        return False

    mid = (L+R)//2

    if (mid+1)*(n-mid+1) == k:

        return True

    elif (mid+1)*(n-mid+1) > k:

        return find(L, mid-1, k)

    elif (mid+1)*(n-mid+1) < k:

        return find(mid+1, R, k)

if find(0, n//2, k):

    print("YES")

else:

    print("NO")