[백준] 20444 색종이가위 python

문제

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

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

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

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

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

입력

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

출력

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

예제 입력 1 복사

4 9

예제 출력 1 복사

YES

---

문제 풀이

1. 색종이에 대한 수학 공식을 파악해야 했다 (나는 실패 ㅠ)

색종이의 개수 = (가로로 자른 수 + 1) * (세로로 자른 수 + 1)

해당 공식으로 개수를 파악한다.

 

2. 가로로 자른 수에 대한 이분탐색 진행

- 초반에 단순하게 가로 , 세로에 대한 이분탐색으로 했었는데 

- 가로값에 대한 최소최대값을 만들고 진행해야했다.

- 가로 최소 0 최대 N//2

 

3. 이분탐색은

start, end 재설정할 때 mid 값 +, - 으로 재설정. 단순히 +1하는게 아니다

 

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

# 색종이를 어떻게 자르는거지

rowS = 0
rowE = n // 2
result = False
while rowS <= rowE:
    mid = (rowS + rowE) // 2
    col = n - mid
    temp = (mid + 1) * (col + 1)
    if (k == temp):
        print("YES")
        result = True
        break
    if (k > temp):
        rowS = mid + 1
    else:
        rowE = mid - 1
        

if not result:
    print("NO")