색종이와 가위
-
[백준]20444: 색종이와 가위 - JAVA문제풀이/백준 2021. 7. 14. 15:07
[백준]20444: 색종이와 가위 20444번: 색종이와 가위 첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 231-1, 1 ≤ k ≤ 263-1) www.acmicpc.net 풀이 🪑 색종이 컷트컷트 하는 문제로 이분탐색을 사용하는 문제였다! 사실 처음부터 이분탐색으로 풀어야겠다 하는 문제는 아니었다. 처음에는 n번으로 자를 수 있는 색종이의 개수를 백트랙킹으로 풀려고 생각했다가 N, K의 범위와 시간제한 0.1초인걸 보고 이분탐색이구나,, 했다. 이제 문제의 조건을 정리해보자. 색종이는 직사각형이며 색종이를 자를 때는 한 변에 평행하도록 자른다. 한 번에 한 경로의 모든 색종이를 다 자른다. 이미 자른 곳은 또 자를 수 없다. 🔧 문제 풀이 순서를 생각해 보자. N에 따른 K를 구할때, 가로로 ..