[ BOJ ][JAVA][20444] 색종이와 가위

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

20444번: 색종이와 가위

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
0.1 초	1024 MB	363	138	118	39.597%

문제

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

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

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

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

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

입력

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

출력

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

예제 입력 1

4 9

예제 출력 1

YES

코드

/**
 * BOJ 20444 색종이와 가위 : Gold 5
 * 이분탐색
 */
import java.io.*;
import java.util.*;

public class p20444 {
    static long n, k;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Long.parseLong(st.nextToken());
        k = Long.parseLong(st.nextToken());

        /**
         * 입력이 long으로 들어오고,
         * 시간제한도 그만큼 빡세보인다.
         * 따라서 logN의 이분탐섹을 사용해보자.
         */

        long lo = 0;
        long hi = n / 2;
        while (lo <= hi) {
            long row = (lo + hi) / 2; // 가로로 싹둑 횟수
            long col = n - row; // 세로로 싹둑 횟수

            long total = cut(row, col);
            if (total == k) {
                System.out.println("YES");
                return;
            } else if (total > k) { // 너무 많이 잘랐기 때문에 가로로 자르는 횟수를 한번 줄여준다.
                hi = row - 1;
            } else {
                lo = row + 1;
            }
        }
        System.out.println("NO");
    }

    // 가로, 세로로 잘랐을 때 반환되는 색종이의 개수
    static long cut(long row, long col) {
        return (row + 1) * (col + 1);
    }
}