BOJ : 20444

1. 문제

 

2. 문제 설명 및 알고리즘 설계

 

색종이를 가로나 세로로 잘라서 원하는 장수의 색종이가 나오는지 확인하는 문제이다.

 

가로나 세로 둘 중 하나를 기준으로 이분탐색을 통해 문제를 해결하면 된다.

 

(자른 횟수+1)*2를 해주면 색종이 장수가 나오는 것을 활용한다.

 

3. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws Exception{
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        long n = Long.parseLong(st.nextToken());
        long k = Long.parseLong(st.nextToken());
 
        String result = "NO";
        long s = 0, e = n / 2 + 1, m, tmp;
        while(s <= e) {
            m = (s + e) / 2;
 
            tmp = (m + 1) * (n - m + 1);
            if(tmp == k) {
                result = "YES";
                break;
            }
            else if (tmp > k) {
                e = m - 1;
            }
            else s = m + 1;
        }
 
        // 출력
        System.out.println(result);
    }
}

 

4. 시간복잡도

O(logN)

 

5. 결과