[G5] 색종이와 가위 : 20444 : JAVA - 이분 탐색

1. 💎 문제

20444번: 색종이와 가위

 

 

 

 

2. 🤔 어떻게 풀까

악 이분 탐색 너무 어렵다!!!! 기준을 못 찾겠어.. 될 때까지 계속 푼다!!!!!😡😡 그래도 이 문제는 기준을 찾았다. 휴 

 

우선 주어진 내용 중 관계를 파악했다. 가위질의 횟수가 많아지면 조각이 증가하고, 가위질의 횟수가 작아지면 조각이 감소할테니, 이를 이용해 계산 값이 주어진 k개의 조각과 딱 맞을 때 가위질의 횟수를 알아낸다.

 

그러기 위해선 가위질에 따른 잘라지는 색종이의 개수를 찾아야한다. 잘 모르겠다가 몇 번 그려보니 `(가로로 자른 수 +1)*(세로로 자른 수 +1)`이 잘라진 조각의 개수인 것을 알았다. 조각이 제일 많이 나올 때는 가로 세로의 개수가 같을 때이고, 제일 적을 때는 한 쪽 변으로만 자를 때이다. 이 것을 바탕으로 min, max를 결정한다.`min = 0`, `max = n`로 한다. 지금은 가로로 자른 수가 기준이다. 이제 코드를 보자

 

 

3.💡  구현 코드

현재 조각의 수는 `(mid+1)*(n-mid+1)`로 알아낸다.

현재 조각이 k개 보다 많다면 가위질 횟수를 낮춰야 하니 max 값을 mid로 변경한다. 

현재 조각이 k개 보다 작다면 가위질 횟수를 높여야 하니 min 값을 mid+1로 변경한다.

 

그리고 현재 조각이 k개와 같다면 바로 YES를 출력하고 종료한다. 사실 여기서 틀렸었다. 같을 때를 따로 처리하지 않고 max값을 mid로 변경하였는데 틀렸었다. 아직 왜그런지는 모르겠다. 이 문제는 사실여부를 따지면 되지 문제이기에 결과를 발견하면 빠져나가는 것이 자연스럽다. 하지만 다른 이분 탐색 문제를 탐색을 끝내고 결과를 출력해서 아무 생각없이 풀었더니 틀렸다. 상황에 따라 잘 생각해야겠다.

 이분 탐색은 사소한 것 여러 개를 모두 완벽하게 생각을 해야 맞아서 어려운 것 같다. 어려워....

 

import java.io.*;
import java.util.Arrays;


public class Solution {
	
    public static void main(String[] args) throws IOException {
    	
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
       String [] nums = br.readLine().split(" ");
       long n = Long.parseLong(nums[0]);
       long k = Long.parseLong(nums[1]);
       
       long min = 0;// 가로(세로)의 길이가 작을 때 개수는 최소
       long max = n; 
       
       while(min <max) {
    	   long mid = (min+max)/2;
    	   
    	   long curK = (mid+1)*(n-mid+1);
    	   
    	   // 원하는 개수보다 많이 잘라질 때 
    	   if(curK > k) {
    		  max = mid;
    	   }
    	   else if(curK == k) {
    		   max = n;
    		   System.out.println("YES");
    		   return;
    	   }
    	   else {
    		   min = mid +1;
    	   }
       }

    bw.write("NO");

       
            
       bw.flush();
       bw.close();
       br.close();

    }
}