자바 [Algorithm] 이분탐색 - 백준 20444 색종이와 가위

1. 문제

 

 

 

2. 접근법

색종이를 N번 잘랐을 때, K개의 색종이를 만들어 낼 수 있는가?

가로로 X번, 세로로 Y번을 자르면 (X+1) * (Y+1) 개의 색종이가 생기게 된다.

가로로 색종이를 자를 횟수를 X라고 하면
세로로 색종이를 자를 횟수는 N-X가 된다.

즉 (X+1) * (N-X+1) = K를 만족하는 X값을 찾는다.

이분탐색을 진행하기 위해
mid = x
y = N-x

 

 

3. 코드

package week09;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Baek20444 {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        long N = Long.parseLong(stringTokenizer.nextToken());
        long K = Long.parseLong(stringTokenizer.nextToken());

        long left = 0;
        long right = N/2;

        while(left <= right){
            long mid = (left + right) / 2;
            long value = (mid +1) * ((N-mid) + 1);

            if(value > K){
                right = mid - 1;
            }else if(value < K){
                left = mid + 1;
            }else{
                System.out.print("YES");
                return;
            }
        }

        System.out.print("NO");
    }
}

 

 

4. 오답노트

 

첫번째 오류는 long형으로 선언했어야 했는데 int형으로 선언해서 오류가 났다.

두번째 오류는 long형으로 선언을 했는데 값을 받을 때 Integer로 받아서 오류가 났다.