[Python] 20444번 색종이와 가위

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

20444번: 색종이와 가위

---

 

23/09/04

 

 

수학을 곁들인 이분 탐색 문제로, 이차방정식의 근의 공식을 떠올린다면 쉽게 해결할 수 있는 문제이다.

 

---

 

문제 접근 방식:

 

 

색종이를 잘라서 나오는 총 색종이 조각의 개수의 규칙을 먼저 관찰할 필요성이 있다.

 

색종이를 총 $N$번 자른다고 하면, 우리는 먼저 가로로만 $N$번 자를 수 있다.

 

그러면 조각이 $N+1$개가 나올 것이라는 사실을 충분히 알 수 있다.

 

마찬가지로, 가로로 $N-1$번, 세로로 $1$번을 자른다고 하면, 가로로 놓여진 $N$개의 조각이 $2$개로 나뉘므로, 조각이 $N*2$개가 나올 것이라는 사실을 알 수 있다.

 

비슷하게, 가로로 $N-2$번, 세로로 $2$번을 자른다고 하면 $(N-1)*3$개의 조각이 나오게 된다.

 

이를 일반화 시키면 $N$번 자르는 횟수가 주어진다면 나올 수 있는 조각의 개수는 $(N+2-x)x$개가 나올 수 있다. (여기서 $x$는 $1 \leq x \leq N+1$에 해당하는 정수이다.)

 

 

따라서, $k = (N+2-x)x$이 성립한다면 $N$번의 가위질로 $k$개의 조각을 만들 수 있다.

 

즉, $x^2 - (N+2)x + k = 0$의 두 근을 $a, b$라고 한다면, 이 두 근이 $1$과 $N+1$범위 사이에 있는 정수라면, 우리는 'YES'를 출력하면 된다.

 

근과 계수의 관계에 의해 $a+b = N+2$임을 알고 있으므로, $a, b$를 $a, N+2-a$로 나타낼 수 있고, 마찬가지로, $k$또한 $a(N+2-a)$로 나타낼 수 있다.

 

$a$의 범위는 $1$부터 $N+1$까지의 정수이고, $N$의 범위는 최대 $2^{31} - 1$까지이므로 이분탐색을 활용해 해당하는 $a$를 찾으면 된다.

 

만약 찾는데 성공한다면 'YES'를, 아니면 'NO'를 출력하면 된다.  

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 20444번 색종이와 가위
# 수학, 이분 탐색
'''
접근 방법:
4 -> 5 (n+1)*1
4 -> 8 (n)*2
4 -> 9 (n-1)*3
...
1(n+1)
(-x+n+2)x where x = 1 to n+1
-x^2 + (n+2)x = k
x^2 - (n+2)x + k = 0
a+b = n+2, a*b = k
k를 소인수분해 한다.
이후 a의 값을 이분 탐색을 통해 찾는다.
'''
def main():
    n, k = map(int, input().rstrip().split())
    start, end = 1, n+1
    while start < end:
        mid = (start+end)//2
        if mid*(n+2-mid) == k:
            print('YES')
            return
        if mid*(n+2-mid) > k:
            end = mid
        else:
            start = mid+1
    print('NO')
    return

main()