Overview
BOJ 20444 색종이와 가위 Python 문제 풀이
분류: Binary Search (이분탐색)
문제 페이지
https://www.acmicpc.net/problem/20444
풀이 코드
from sys import stdin
def main():
n, k = map(int, stdin.readline().split())
start, end = 0, n // 2
papers = 0
while start <= end:
mid = start + (end - start) // 2
papers = (mid + 1) * (n - mid + 1)
if papers < k:
start = mid + 1
elif papers > k:
end = mid - 1
else:
break
print(['NO', 'YES'][papers == k])
if __name__ == "__main__":
main()
이분탐색을 이용하여 가로 방향 자르기 횟수를 조정한다.
n번의 가위질로 종이 조각을 가장 많이 생성하는 방법은 가로 방향으로 n / 2 번, 세로 방향으로 n / 2 번 가위질하는것이다. 따라서 가로 방향 가위질 횟수를 최소 0번, 최대 n // 2번으로 잡아 start, end 변수를 초기화한다. 그 다음 이분 탐색을 통해 가로 방향 가위질 횟수를 조정하며 k 개의 종이 조각이 생성가능한지 탐색한다.
추가) 이분탐색에서 'mid = start + (end - start) // 2' 으로 작성한 이유
위 백준 문제 풀이 코드에서 이진탐색을 진행할 때, 중간 값을 구하는 코드를
mid = start + (end - start) // 2으로 작성하였다. 같은 기능을 아래 코드처럼 더 짧게 표현 가능하다.
mid = (start + end) // 2그러나 다른 이분탐색에서 위와 같이 코드를 작성하면, 경우에 따라 오버플로우 버그가 발생할 수 있다. 따라서 첫 번째 코드와 같이 작성하는 습관을 들이기 위해 두 번째 코드를 사용하지 않았다. 자세한 내용은 아래 링크 참고
