백준 20444 색종이와 가위

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

 

#include <iostream>

using namespace std;



int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    long long n, k;

    cin >> n >> k;


    //n을 w, h에 적절히 분배->w*h=k가 되어야 함
    //mid: w에 분배할 가위질 수->h에 분배할 가위질 수=n-mid

    long long l = 0;
    long long r = n / 2;

    while (l <= r) {

        long long mid = (l + r) / 2;

        //width=w*h
        long long width = (1 + mid) * (1 + (n - mid));

        if (width == k) {
            cout << "YES";
            return 0;
        }

        if (width < k) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }


    }

    cout << "NO";


    return 0;
}

 

1. 문제

색종이가 있다. 이 색종이를 n번 가로 또는 세로로 가위질하여 총 k 개의 색종이를 만들 수 있는 지 여부를 구하는 문제이다.

2. 풀이

 1개의 색종이가 있고 다음의 입력이 주어졌다고 가정하자.

4 9

 색종이를 가로로 두 번, 세로로 두 번 자르면 가로 색종이 3개, 세로 색종이 3개로 총 9개의 색종이를 만들 수 있다.

 색종이를 자르면 자른 방향의 색종이가 하나 늘어나므로 이처럼 계산하면 색종이를 n번 잘랐을 때 색종이의 개수를 계산하는 방법은 다음과 같다.

 (1+가로로 자른 횟수)*(1+세로로 자른 횟수)

이를 기반으로 이분 탐색을 돌려 계산한다.

    //n을 w, h에 적절히 분배->w*h=k가 되어야 함
    //mid: w에 분배할 가위질 수->h에 분배할 가위질 수=n-mid

    long long l = 0;
    long long r = n / 2;

 정사각형의 색종이를 잘라 그 곱을 계산하면 한 부분의 색종이를 자른 횟수가 n/2를 넘어가면 색종이의 개수가 역으로 줄어든다. 따라서 범위를 위와 같이 잡고 이분 탐색을 실행한다.

    while (l <= r) {

        long long mid = (l + r) / 2;

        //width=w*h
        long long width = (1 + mid) * (1 + (n - mid));

        if (width == k) {
            cout << "YES";
            return 0;
        }

        if (width < k) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }


    }

    cout << "NO";

 

mid는 색종이를 가로로 자른 횟수이다. 이러면 전체 n번 잘라야 하므로 색종이를 세로로 자른 횟수는 n-mid가 된다. 이를 위의 공식에 대입하면 넓이를 구할 수 있다.

 해당 넓이가 k와 일치하면 n번의 가위질로 k개의 색종이를 만들 수 있다는 뜻이므로 YES를 출력한다. 그렇지 않다면

넓이가 작을 경우 0~n/2의 범위에서 mid가 커져야 전체 색종이의 개수가 늘어나므로 mid보다 큰 범위에 대해 이분탐색을 실행하고, 반대의 경우 mid보다 작은 범위에 대해 이분 탐색을 실행한다.

 이분탐색을 빠져나간 후에도 k개의 색종이를 만들지 못했다면 NO를 출력하면 정답을 구할 수 있다.