[백준/BOJ] gold5 - 20444번 색종이와 가위

▶20444 - 색종이와 가위

백준 로고

 

▶문제

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

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

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

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

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

 

▶입력

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

 

▶출력

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

728x90

▶풀이

이분배열로 풀면 되는 문제이다.

가로, 세로로 나눠서 자를 때, 전체 조각의 수는 (가로 + 1) * (세로 + 1)이 된다.

 

가로 혹은 세로를 0 ~ n으로 나누면 되지만, 대칭이기 때문에 0 ~ n // 2까지만 하면 된다.

left를 0, right를 n // 2로 하고 이분탐색을 하면 된다.

n, k = map(int, input().split())
left = 0
right = n // 2

check = False

while left <= right:
    mid = (left + right) // 2
    piece = (mid + 1) * (n - mid + 1)

    if piece == k:
        print('YES')
        check = True
        break

    if k > piece:
        left = mid + 1
    else:
        right = mid - 1


if not check:
    print('NO')