문제
오늘도 역시 준성이는 어김없이 색종이와 쿼리를 푸는 데 실패하였다!!
색종이에 열등감을 느낀 준성이는 가위로 눈에 보이는 색종이를 모두 잘라 버리려고 한다!!
색종이를 자를 때는 다음과 같은 규칙을 따른다.
1. 색종이는 직사각형이며, 색종이를 자를 때는 한 변에 평행하게 자른다.
2. 자르기 시작했으면, 경로 상의 모든 색종이를 자를 때까지 멈추지 않는다.
3. 이미 자른 곳을 또 자를 수 없다.
분노에 찬 가위질을 하던 준성이는 갑자기 하나의 색종이를 정확히 n번의 가위질로 k개의 색종이 조각으로 만들 수 있는지 궁금해졌다.
궁금하지만 화가 나서 코딩에 집중할 수 없는 준성이 대신 코드를 작성해주도록 하자.
import sys
input = lambda: sys.stdin.readline().strip()
# start = 0, end = n
# 세로 가위질 : mid
# 가로 가위질 : n - mid
# 색종이 조각 > k : end = mid - 1
# 색종이 조각 < k : start = mid + 1
# 색종이 조각 == k : YES
n, k = map(int, input().split())
start, end = 0, n
check = "NO"
while start <= end:
mid = (start + end) // 2
a, b = mid, n - mid
num = (a + 1) * (b + 1)
if num == k:
check = "YES"
break
elif num > k:
end = mid - 1
else:
start = mid + 1
print(check)풀이
- 색종이 조각 : (세로 가위질 + 1) * (가로 가위질 + 1)
- start, end = 0, n
- 세로 가위질 : mid
- 가로 가위질 : n - mid
- 색종이 조각 > k : end = mid - 1
- 색종이 조각 == k : YES
- 색종이 조각 < k : start = mid + 1
