[Python/파이썬] 백준 20444번 색종이와 가위

20444번: 색종이와 가위

 

문제

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

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

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

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

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

입력

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

출력

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

코드

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

start, end = 0, n//2+1
while start <= end:
    mid = (start+end) // 2
    piece = (n+1-mid) * (mid+1) # 조각 개수
    if piece == k:
        print("YES")
        exit()
    if piece > k:
        end = mid - 1
    else:
        start = mid + 1
        
print("NO")

 

색종이를 가로, 세로에 평행하게 총 n번 잘라서 만들 수 있는 조각의 수는 (n+1-mid) * (mid+1)개이다. 우리는 이 값이 정확히 k가 되는 mid 값이 있는지 이분탐색을 이용하여 찾으면 된다.