문제 풀이
이분 탐색
isPossible = 색종이를 n번 잘라 나오는 조각의 총 갯수가 k개가 될 수 있는지 여부
left = 색종이를 수직으로 자르는 횟수의 이분 탐색 최소 범위
right = 색종이를 수직으로 자르는 횟수의 이분 탐색 최대 범위
색종이는 수직 또는 수평 방향으로 자르고 총 n번 자른다고 했으므로 수직으로 자르는 횟수에 따라 수평으로 자른 횟수가 정해짐
수직으로 자르는 횟수가 a라면 수평으로 자르는 횟수는 n - a이고 이 때 각각 a + 1, n - a + 1의 영역으로 나뉜 격자 형태로 조각이 나오므로 조각의 총 갯수는 (a + 1) * (n - a + 1)개가 됨
a가 n / 2가 넘어가는 순간 수직, 수평으로 자르는 횟수가 뒤바뀔뿐이므로 총 갯수는 이미 계산한 결과가 나옴
따라서 a를 0부터 n / 2까지만 검사하면 됨
총 갯수가 위로 볼록한 이차함수 식이 되고 축이 n / 2이므로 검사하는 범위 0부터 n / 2까지는 a가 커질수록 총 갯수도 커짐
그러므로 0부터 n / 2까지의 범위를 이분탐색하며 총 갯수가 k개가 될 수 있는지 검사하면 됨
이렇게 이분탐색으로 검사해 총 갯수가 k개가 될 수 있는지 여부를 isPossible에 저장하고 이에 따라 YES, NO를 출력하면 정답
풀이 설명
색종이를 자른 부위를 다시 자르지 않도록 평행하게 n번 자른다고 할 때 남는 색종이 조각이 k개가 될 수 있는지 판별하는 문제이다.
자르는 방향이 수직, 수평 방향으로 나뉘므로 수직 방향으로 자르는 횟수를 a번이라고 하면 수평 방향으로는 n - a번을 잘라야 한다. 이렇게 자르면 수직 방향으로 a + 1개의 영역, 수평 방향으로 n - a + 1개의 영역으로 구분되는 격자 형태가 되므로 총 갯수는 이 둘을 곱한 수가 된다.
그럼 이제 수직 방향으로 자르는 횟수 a에 대해 잘리는 총 조각의 갯수가 정해진다는 것을 알 수 있으니 이 a의 범위를 확인해야 하는데 이는 0부터 n / 2라고 할 수 있다.
a가 0부터 n까지라고 생각할 수 있는데 수평 방향으로 자르는 횟수가 n - a번이므로 사실상 n / 2를 넘어서는 순간부터는 수직, 수평 방향이 횟수가 바뀌기만 하고 잘리는 총 갯수는 동일한 갯수가 다시 나오기 때문에 계산할 필요가 없다.
그리고 총 갯수가 (a + 1) * (n - a + 1)의 위로 볼록한 이차함수 형태를 띄우기 때문에 중앙의 축부분이 가장 높고 축에서 멀어질 수록 값이 작아진다는 점을 알 수 있다. 이 때 축을 계산한다면 n / 2가 된다는 것을 알 수 있다.
따라서 계산해야 하는 범위 0부터 n / 2까지는 a가 커질수록 총 갯수도 커진다는 점을 알 수 있고, n의 범위가 상당히 크기 때문에 총 갯수가 k가 될 수 있는지를 이분 탐색으로 확인할 수 있다.
이분 탐색을 하기 위해 현재 범위의 최솟값을 left, 최댓값을 right로 정의하고 각각 0과 n / 2 값으로 초기화한다. 그 이후에 정확히 k가 되는 값을 찾았는지를 저장하기 위한 변수 isPossible을 정의하고 가능한지 이제 찾아야 하는 것이므로 false로 초기화 한다.
그 이후에 현재 확인하는 값이 범위의 중간값이므로 이를 계산한 mid에 대해 수직 방향으로 mid번 잘랐을 때의 총 갯수 count를 계산하고 이 값이 k보다 크다면 mid보다 더 큰 값에 대해 확인할 필요가 없으니 right에 mid - 1을 대입해 더 작은 값의 범위를 확인한다.
만약 count가 k와 같다면 원하는 값을 찾은 것이므로 isPossible에 true를 대입하고 반복문을 탈출하면 된다.
count가 k보다 작다면 mid보다 더 큰 값의 범위를 찾아야 하는 것이므로 left에 mid + 1을 대입해준다. 이 반복문은 필요한 모든 범위를 확인해야 하므로 left가 right 이하일 때 반복하면 된다.
그렇게 반복문을 탈출했을 때 isPossible이 true라면 조각의 갯수가 k가 되는 값을 찾은 것이므로 YES, false라면 조각의 갯수가 k가 될 수 없는 것이므로 NO를 출력하면 정답이 된다.
소스 코드
import java.util.StringTokenizer
fun main() = System.`in`.bufferedReader().run {
val st = StringTokenizer(readLine())
val n = st.nextToken().toLong()
val k = st.nextToken().toLong()
var left = 0L
var right = n / 2
var isPossible = false
while(left <= right){
val mid = (left + right) / 2
val count = (mid + 1) * (n - mid + 1)
if(count > k){
right = mid - 1
} else if(count == k){
isPossible = true
break
} else {
left = mid + 1
}
}
println(if(isPossible) "YES" else "NO")
}