20444(색종이와 가위) - 해결

색종이와 가위

 

문제

오늘도 역시 준성이는 어김없이 색종이와 쿼리를 푸는 데 실패하였다!!

색종이에 열등감을 느낀 준성이는 가위로 눈에 보이는 색종이를 모두 잘라 버리려고 한다!!

색종이를 자를 때는 다음과 같은 규칙을 따른다.

1. 색종이는 직사각형이며, 색종이를 자를 때는 한 변에 평행하게 자른다.
2. 자르기 시작했으면, 경로 상의 모든 색종이를 자를 때까지 멈추지 않는다.
3. 이미 자른 곳을 또 자를 수 없다.

분노에 찬 가위질을 하던 준성이는 갑자기 하나의 색종이를 정확히 n번의 가위질로 k개의 색종이 조각으로 만들 수 있는지 궁금해졌다.
궁금하지만 화가 나서 코딩에 집중할 수 없는 준성이 대신 코드를 작성해주도록 하자.

 

입력

첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 231-1, 1 ≤ k ≤ 263-1)

 

출력

첫 줄에 정확히 n번의 가위질로 k개의 색종이 조각을 만들 수 있다면 YES, 아니라면 NO를 출력한다.

---

처음엔 어떻게 해야할지 고민하였지만 핵심은 자르는 방식!

색종이를 자르는 건 한 변에 평행하게 자르기 때문에 세로 혹은 가로로 자르는 방식이 있다는 것.

이를 잘 파악해야한다. 한 쪽 방향으로만 자르면 1개씩 늘어난다. 하지만 교차해서 자르면 2배로 증가한다는 것.

그리고 또한 순서와 상관없이 가로와 세로만 구분하면 갯수가 똑같다는 것.

(가로, 가로, 세로)와 (가로, 세로, 가로)로 잘라도 같은 갯수로 만들어 진다는 것이다.

그리고 총 횟수가 가로와 세로의 합이다. 

또한, 자르는 횟수가 대칭하다는 것 총 횟수가 5 번이면

가로	0	1	2	3	4	5
총 갯수	6	10	12	12	10	6

총 횟수가 6번이면

가로	0	1	2	3	4	5	6
총 갯수	7	12	15	16	15	12	7

이렇게 대칭해서 N//2를 사용하여 0 ~ N//2 구간을 이분 탐색을 하면된다.

 

import sys
input = sys.stdin.readline

N, K = map(int,input().split())

# 이분 탐색
def bs(st,ed):
    while st <= ed:
        m = (st + ed)//2
        # 총 갯수를 계산
        # 총 갯수는 (가로 + 1) * (세로 + 1)
        A = (N - m + 1) * (m + 1)
        # K와 같다면
        if A == K:
            return "YES"
        # 작으면 오른쪽확인
        if A < K:
            st = m + 1
        # 크면 왼쪽확인
        else:
            ed = m - 1
    # 못찾으면 NO
    return "NO"

# 총 갯수가 대칭하기 때문에 반으로 나누어서 확인
print(bs(0,N//2))