[백준] 20444번: 색종이와 가위(이분탐색, Python)

문제 링크

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

20444번: 색종이와 가위

 

풀이

풀이 설명

* 분류: 이진탐색

• n번의 가위질을 할때 만들어지는 조각의 경우의 수를 정하는 기준은 가로로 몇번, 세로로 몇번 자르는지에 따라 달라진다. 
• 예를 들어, 3번 자를 경우
  • 1) 세로로 3번 자르는 경우 -> 4조각
  • 2)세로로 1번 가로로 2번 자르는 경우 -> 6조각이 나온다. 
• 따라서 가로: row, 세로: col(n-row) 로 친다면, total(조각수) = (row + 1)(col + 1) 이므로,
• row를 기준으로 탐색한다고 하면 mid 값으로 설정할 수 있다.

풀이 코드

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

length = n // 2

start = 0
end = length
ans = 'NO'
while start <= end:
    mid = (start + end) // 2

    total = (mid + 1) * (n - mid + 1)
    if total == k:
        ans = 'YES'
        break
    elif total < k:
        start = mid + 1
    else:
        end = mid - 1

print(ans)