[백준] Python - 색종이와 가위

20444번: 색종이와 가위

 

색종이와 가위 문제다.

이진탐색 문제라고는 하지만 이진탐색을 쓸 필요는 없다.

색종이를 잘랐을때 입력한 값 만큼의 사각형이 나오는지 판단하는 문제이다.

 

여기서 규칙이 하나 생기는데 

x를 가로로 자르는 횟수, y를 세로로 자르는 횟수, n을 총 자르는 횟수, k를 잘랐을 때 나오는 사각형의 총 개수라고 하면

1) x + y = n

2) (x+1)(y+1) = k가 성립한다.

 

여기서 1)에서 x = n - y를 2)에 대입하면 x에 대한 2차 방정식이 나온다.

사각형의 개수는 무조건 자연수일 수 밖에 없으니 이 2차 방정식을 근의 공식을 통해 해가 자연수로 나오는지 확인하면 된다.

 

import sys
import math as m

def quadratic_formula(cut, rect):
    poly = cut ** 2 + 4*cut - 4*rect + 4
    #cut == n
    #rect == k

    if poly < 0 :
        print("NO")
        return
    #1.1   1 != 1.1
    if int(poly) != poly:
        print("NO")
        return

    if int((poly**(1/2))) ** 2 != poly:
        print("NO")
        return

    result1 = (cut+2 + (poly**(1/2))) / 2
    result2 = (cut+2  - (poly**(1/2))) / 2

    if int(result1) != result1 or int(result2) != result2:
        print("NO")
        return

    if (result1 > 0) and (result2 > 0):
        print("YES")
        return
    else:
        print("NO")
        return

n, k = map(int, sys.stdin.readline().split())
quadratic_formula(n, k)