백준 20444 색종이와 가위 Kotlin (이분 탐색)

문제 출처: https://www.acmicpc.net/problem/20444

20444번: 색종이와 가위

문제

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

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

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

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

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

입력

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

출력

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

알고리즘 분류

• 수학
• 이분 탐색

풀이

가로 세로로 자를 때 늘어나는 색종이의 규칙을 보면,

(x+1) * (y+1) = 색종이의 개수 

//가로로 자른 횟수 x, 세로로 자른 횟수 y

라는 식이 성립된다.

우리는 N번 잘라서 k를 만들어야 하기 때문에, x가 1이라면 y는 N-1, x가 3이라면 y는 n-3

즉 한 축으로 자른 횟수를 정하면 다른 축으로 자른 횟수도 정해지기 때문에, 하나의 축을 기준으로 정답을 탐색하면 된다.

그럼 x축을 기준으로 정답을 찾는다고 할 때, 이 문제에서 일반적인 선형 탐색을 한다면 O(2^31)의 시간 복잡도로 시간 초과가 나올 것이다. 따라서 이분 탐색 O(log2^31)으로 시간 내에 답을 찾을 수 있다.

N이 6이라 할 때, x가 2이면 y는 4, x가 4이면 y는 2, 즉, x의 최댓값은 N/2, x의 최솟값은 0이 된다.

우리는 x를 기준으로 탐색을 하기로 했으니, 이분 탐색의 start = 0, end =N/2로 잡고,

(mid+1) * (N-mid+1) = result(x가 mid일 때 색종이의 수)

이 result가 k보다 작다면 x를 늘리고, k보다 크다면 x를 줄이면 된다.

 

코드

val br = System.`in`.bufferedReader()

fun main() = with(System.out.bufferedWriter()){

    //input
    val (n,k) = br.readLine().split(" ").map{it.toLong()}

    //solve, output
    //x를 기준으로 이분 탐색
    var s = 0
    var e = n.toInt()/2
    while(s<=e){
        val mid = (s+e)/2
        val result = (mid+1) * (n-mid+1)
        if(result == k){
            write("YES")
            close()
            return
        }
        else if(result <k){
            s = mid+1
        }
        else{
            e = mid-1
        }
    }
    write("NO")

    close()
}