[Boj_20444] 색종이와 가위

📎 문제 링크

https://www.acmicpc.net/problem/20444

 

▸ 문제

오늘도 역시 준성이는 어김없이 색종이와 쿼리를 푸는 데 실패하였다!!

색종이에 열등감을 느낀 준성이는 가위로 눈에 보이는 색종이를 모두 잘라 버리려고 한다!!

색종이를 자를 때는 다음과 같은 규칙을 따른다.

1. 색종이는 직사각형이며, 색종이를 자를 때는 한 변에 평행하게 자른다.
2. 자르기 시작했으면, 경로 상의 모든 색종이를 자를 때까지 멈추지 않는다.
3. 이미 자른 곳을 또 자를 수 없다.

분노에 찬 가위질을 하던 준성이는 갑자기 하나의 색종이를 정확히 n번의 가위질로 k개의 색종이 조각으로 만들 수 있는지 궁금해졌다.
궁금하지만 화가 나서 코딩에 집중할 수 없는 준성이 대신 코드를 작성해주도록 하자.

 

▸ 입력

첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 231-1, 1 ≤ k ≤ 263-1)

 

▸ 출력

첫 줄에 정확히 n번의 가위질로 k개의 색종이 조각을 만들 수 있다면 YES, 아니라면 NO를 출력한다.

 

📍 문제 정보

• 🥇 문제 레벨 : 골드 5
• 🔔  문제 유형 : 수학, 이분 탐색
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

이분 탐색으로 해결할 수 있는 문제였다.

 

가로 또는 세로를 기준으로 색종이를 자른다고 할 때, 그 자르는 횟수에 따라 색종이의 조각 수가 결정된다.

 

자르는 횟수의 최솟값은 0, 최댓값은 N/2로 설정한다.

예를 들어, 가로로 자른 횟수와 세로로 자른 횟수가 아래와 같다고 해보자.

가로로 자른 횟수	세로로 자른 횟수
0	N
N	0
N/2	N/2

즉, 가로와 세로는 대칭을 이루므로 N/2까지만 탐색하면 된다.

 

나의 경우는 가로로 자른 횟수를 기준으로 탐색을 진행했다.

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

잘리는 색종이의 총 개수 : (가로로 자른 횟수+1)*(세로로 자른 횟수+1)

 

색종이의 총개수 total이 k와 같다면, n 번의 가위질로 k 개의 색종이 조각을 만들 수 있으므로 YES 출력하고 탐색을 종료한다.

total > k라면, 색종이 조각이 넘치므로 더 크게 잘라 개수를 줄여준다. 즉, row 값을 줄인다.

total < k라면, 색종이 조각이 부족하므로 더 작게 잘라 개수를 늘려준다. 즉, row 값을 늘린다.

 

탐색이 끝날 때까지 total과 k가 같지 않다면 NO를 출력한다. 즉, n 번의 가위질로 k 개의 색종이 조각을 만들 수 없는 것이다.

 

위 풀이를 코드로 작성해 보면 아래와 같다.

 

✔ 최종 코드

메모리 : 11532KB
시간 : 72ms

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());
        // n번의 가위질로 k개의 색종이 조각을 만들 수 있는지
        long n = Long.parseLong(st.nextToken());
        long k = Long.parseLong(st.nextToken());
        
        long start = 0; // 자르는 횟수의 최솟값
        long end = n/2; // 최댓값
        while (start <= end) {
            // 가로로 몇 번 잘랐는지를 기준으로 둔다.
            long row = start + (end - start) / 2;
            long col = n-row;

            // 자른 색종이 조각의 총 개수
            long total = getTotal(row, col);
            if (total == k) { // 조건 만족
                System.out.println("YES");
                return;
            } else if (total > k) { // 색종이 조각 넘침, 더 크게 잘라야 함
                end = row-1;
            } else { // 색종이 조각 부족, 더 작게 잘라야 함
                start = row+1;
            }
        }

        System.out.println("NO");
    }

    private static long getTotal(long row, long col) {
        return (row+1)*(col+1);
    }
}

 

문제를 읽고 이분 탐색을 떠올리는 게 쉽지 않다. 또 어떤 값을 기준으로 탐색을 진행해야 할지 찾는 것도 어렵다. 😭

입력으로 주어진 값의 범위가 크고 시간제한이 작다면 이진 탐색 먼저 떠올려야겠다 !

 

어찌저찌 해결 완료 ! 🔥