백준 20444번: 색종이와 가위

백준 20444번: 색종이와 가위

원래는 이분탐색을 풀려고 시작했던 문제인데, 그냥 방정식으로도 풀 수 있을 것 같아서 방정식으로 풀었다.

import math
n,k = map(int,input().split())
check = n*n - 4*(k-n-1)
if check>=0:
    ans_1 = (n+math.sqrt(check))/2
    ans_2 = (n-math.sqrt(check))/2
    if int(math.sqrt(check))**2==check and ans_1.is_integer() and ans_2.is_integer() and ans_1>=0 and ans_2>=0:
        print("YES")
    else:
        print("NO")
else:
    print("NO")

math.sqrt(check).is_integer()으로 해서 계속 틀렸는데, math.pow(math.sqrt(check),2)==check로 해도 안되고, int(math.sqrt(check))**2=check 저렇게 해야 된다. 아마 부동소수점관련 문제가 아니려나 싶기는함. 이 문제는 이분탐색으로 풀 수도 있어서 이분탐색 풀이를 찾아봤다.

n, k = map(int, input().split())
left = 0
right = n // 2
isPossible = False

while left <= right:
    rowCut = (left + right) // 2
    colCut = n - rowCut
    pieces = (rowCut + 1) * (colCut + 1)
    if k == pieces:
        print('YES')
        isPossible = True
        break
    if k > pieces:
        left = rowCut + 1
    else:
        right = rowCut - 1

if not isPossible:
    print('NO')

max값을 n까지 잡으면 되나? 했는데 대칭적이니까 n/2로만 잡아도 되는 것 같다.