[알고리즘] 백준 - 색종이와 가위

백준 - 색종이와 가위

다른 사람 풀이

import sys
sys.setrecursionlimit(10**6)

n, k = map(int, input().split()) # n번의 가위질, k개의 색종이

left, right = 0, (n // 2) + 1

def get_partitioned_paper(horizontal_cut):
    return (horizontal_cut + 1) * (n - horizontal_cut + 1)

while left <= right:
    mid = (left + right) // 2
    if get_partitioned_paper(mid) == k:
        print("YES")
        sys.exit(0)
    if get_partitioned_paper(mid) > k:
        right = mid - 1
    else:
        left = mid + 1

print("NO")

n의 범위가 매우 크므로 이분 탐색이라고 힌트를 얻을 수 있어야 한다. n번의 가위질은 h번의 가로 자르기와 n-h번의 세로자르기로 이루어져 있다. h번의 가로 자르기와 n-h번의 세로자르기는 (h + 1) * (n - h + 1)개의 작은 종이들을 만든다. 그래서 가로 자르기 h를 몇번 할지 정하면 세로 자르기는 자동으로 정해진다.

가로 자르기는 n보다 작아야 하지만, 더 효율적으로 풀려면 (n // 2) + 1보다 작아야한다. 가로로 h번, 세로로 (n -h)번 자르는 것과 가로로 (n-h)번 자르고 세로로 h번 자르는 것은 같기 때문이다.

https://david0506.tistory.com/34
https://hbj0209.tistory.com/141