[백준]20444: 색종이와 가위 - JAVA

[백준]20444: 색종이와 가위

20444번: 색종이와 가위

풀이

🪑 색종이 컷트컷트 하는 문제로 이분탐색을 사용하는 문제였다!

 

사실 처음부터 이분탐색으로 풀어야겠다 하는 문제는 아니었다.

처음에는 n번으로 자를 수 있는 색종이의 개수를 백트랙킹으로 풀려고 생각했다가 N, K의 범위와 시간제한 0.1초인걸 보고 이분탐색이구나,, 했다.

 

이제 문제의 조건을 정리해보자.

• 색종이는 직사각형이며 색종이를 자를 때는 한 변에 평행하도록 자른다.
• 한 번에 한 경로의 모든 색종이를 다 자른다.
• 이미 자른 곳은 또 자를 수 없다.

 

 

🔧 문제 풀이 순서를 생각해 보자.

• N에 따른 K를 구할때, 가로로 자른 횟수와 세로로 자른 횟수에 따라 K값이 달라진다. 그러므로 가로로 몇 번 잘랐는지를 기준값으로 정해 이분탐색을 해 준다.
• 이때 범위는 0 ~ N/2로 정한다. 가로로 자른 횟수와 세로로 자른 횟수가 바뀌어도 결과 값에는 영향이 없기 때문이다.

 

 

🔹 이분탐색을 한다.

- 나는 기준값을 가로로 자른 횟수를 설정해 주었다.

- 이때 세로로 자른 횟수도 구하여 이를 가지고 잘리는 색종이의 개수를 계산해 주었다.

- row, col일때 결과는 (row + 1) * (col + 1)이 나온다.

- 결과 값이 찾고자 하는 K와 같다면 YES를 출력해 주고 탐색을 끝낸다.

- 결과 값이 K보다 크다면 row, col의 차이를 더 크게하여 잘리는 색종이의 개수를 줄여준다.

- 결과 값이 K보다 작다면 row, col의 차이를 더 작게해 잘리는 색종이의 개수를 많아지게 한다.

 

코드

import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        long n = scan.nextInt();
        long k = scan.nextLong();
 
        long left = 0;
        long right = n / 2;
        while(left <= right) {
            long row = (left + right) / 2;
            long col = n - row;
 
            long total = cut_paper(row, col);
            if(total == k) {
                System.out.println("YES");
                return;
            } else if(total > k) { //row col의 차이가 더 커야한다.
                right = row - 1;
            } else if (total < k){
                left = row + 1;
            }  
        }
        System.out.println("NO");
    }
 
    public static long cut_paper(long row, long col) {
        return (row + 1) * (col + 1);
    }
}