20444 색종이와 가위

 

 

1. 풀이

 

다른 블로그를 참고했다.

이분탐색으로 풀면 된다.

 

 

1) 예제

 

먼저 아래와 같은 경우를 생각해보자.

 

 

4 5

 

4 = n, 5 = k

=> 4번의 가위질로 5개 색종이 조각을 만들 수 있는지 확인해야 한다.

 

 

 

이분탐색 변수로 left, right, mid 를 사용한다.

 

처음에는 다음과 같다.

left = 0

right = n

mid = (left + right) / 2 

 

여기서 mid는 색종이를 세로로 자른 횟수가 된다.

즉, 여기서는 left = 0, right = 4 이므로

mid = 2 가 된다. 즉 세로로 2번 자르고,

가로는 총 4번의 가위질에서 2번을 제외한, 2번 자르게 된다.

 

 

2) 색종이를 자른 후 총 개수

 

처음 아래와 같은 상태에서

                                                                     

세로로 1번 자르면 색종이가 2개가 된다.

이 상태에서 가로로 1번 자르면 색종이가 4개가 된다.

 

즉, 색종이 개수는 (가로로 자른 횟수 + 1 ) * (세로로 자른 횟수 +1 ) 가 된다.

처음에 세로로 1번 잘랐을 때는 1 * 2 = 2

두번째는 가로 1번, 세로 1번 자른 상태이므로 2 * 2 = 4 가 된다.

 

그러면 위의 예제는 mid =2 로,

세로로 2번, 가로로 2번 자른다고 했으므로 

색종이 총 개수는 3 * 3 = 9 가 된다.

 

우리는 5개의 색종이를 만들어야 하는데, 9개가 만들어졌기 때문에 색종이 개수를 줄여야 한다.

그러려면 다음과 같이 한다.

 

 

3) 색종이 조각 개수를 줄이는 방법

 

예를 들어 색종이를 총 3번 자른다고 하자.

만약 세로로만 3번 자르면, 총 색종이는 4개이다.

 

하지만 세로로 2번, 가로로 1번 자르면 3 * 2 = 6 개가 된다.

즉, 한 방향으로 많이 자를수록 색종이 개수가 작다.

 

그렇다면 색종이 개수를 줄이려면 mid, 즉 세로로 자르는 횟수를 줄인다. 

색종이 자르는 횟수는 총 n으로 고정되어 있기 때문에, 세로로 자르는 횟수가 줄면

가로로 자르는 횟수는 더 늘어난다.

 

즉, 한 방향으로 더 많이 자르게 되고

총 색종이 개수가 줄어든다.

 

mid = (left + right) / 2 이기 때문에 

right = mid -1 로 줄여준다.

그러면 줄어든 right 로 다시 mid를 구하기 때문에, mid는 줄어든다. 

 

위에서 mid = 2였기 때문에 right = 1 이 된다.

left = 0 이다.

 

그러면 mid = 0 이다.

(mid 는 long 형 이기 때문에 (1 + 0) / 2 = 0.5 이지만 정수만 저장된다)

 

즉, 세로로 0번 자르고, 가로로는 4 - 0 = 4번 자른다.

그러면 색종이 개수는

5 * 1 = 5 가 된다.

따라서 원하는 정답을 찾게 된다.

 

 

2. 최종 코드 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int n = Integer.parseInt(st.nextToken());
		long k = Long.parseLong(st.nextToken());	
		
		long left = 0;
		long right = n;
		long sum = 0;
		
		String result = "NO";
		
		while(left <= right) {
		
			long mid = (left + right)/2;
	
			sum = (mid+1) * (n-mid+1);
	
			if(sum == k) {
				
				result = "YES";
				break;
				
			}else if(sum <k ) {
			
				left = mid +1;
			
			}else {
				
				right = mid -1;
			}		
		}
		
		System.out.println(result);
		
	}
}

참고 블로그 : 

https://moonsbeen.tistory.com/303

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