[백준] 20444번: 색종이와 가위 (파이썬/Python) - 이진탐색

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

20444번: 색종이와 가위

i) 규칙 찾기 

n=4일때 가능한 모든 경우를 보면 
(col, row) = (0, 4), (1, 3), (2, 2) (3, 1), (4, 0) 이다 
근데 column , row 구분을 안해줘도 되는 이유가, 만들어지는 색종이의 개수만 확인하면 되기 때문이다. -> 즉 0 부터 n//2 까지의 경우만 확인해주면 시간을 줄일 수 있다. 

만들어 지는 색종이의 개수는 (col+1) * (row+1) 이다. 

또한 찾을 수 있는 규칙은, column 개수와 row의 개수 차이가 클수록 만들어지는 색종이의 개수가 줄어들고, column 개수와 row 개수 차이가 작을 수록 만들어지는 색종이의 개수가 증가한다.

ii) binary search 적용하기 
start, end 의 중간 값인 mid와 target값을 비교한다. 
이 문제의 경우 만들어진 색종이의 개수를 확인해 주어야 하므로, 위에서 찾아낸 공식에 의하면 

(mid+1) * (n-mid+1) = 색종이의 개수    이다. 

색종이의 개수가 target보다 크면, 가로와 세로 개수의 차이를 늘려야 한다.
row 값을 mid-1로 갱신해 준다. (binary search 에서 흔히 end에 해당)

반대로 색종이의 개수가 target보다 작으면, 가로와 세로 개수의 차이를 줄여서 box의 개수를 늘리는 col, row 쌍을 찾아야 한다. 
col 값을 mid+1로 갱신해준다. 

import sys

input = sys.stdin.readline

n, target = map(int, input().split())
flag = False

def binary_search():
    global flag
    col = 0 # start
    row = n // 2 # end ---> n=4 일 때 (0, 4), (1, 3), (2, 2) 이므로 n//2까지만 탐색해도 모든 케이스 확인 가능 !
    while col <= row:
        mid = (row+col)//2
        box = (mid+1) * (n-mid+1)
        if box == target:
            print("YES")
            flag = True
            break
        if box < target: # 칸을 늘리기 위해서는 가로와 세로 개수의 차이를 줄여야 한다.
            col = mid+1
        else:
            row = mid -1
             # 칸을 줄이기 위해서는 가로와 세로 개수의 차이를 늘려야 한다.

binary_search()
if not flag:
    print("NO")