BOJ 20444 색종이와 가위

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

20444번: 색종이와 가위

 

 

 

 

색종이를 $N$번 잘라서 $k$개의 조각으로 나눌 수 있는지 묻는 문제이다. 이 문제를 해결하는 방법으로 이분 탐색을 이용하는 방법, 이차방정식의 판별식을 이용하는 방법을 이용할 것이다. 먼저 이분탐색을 해결하는 방법을 설명하겠다.

색종이는 변에 평행하게 자를 수 밖에 없으므로 가로로 자르는 횟수를 $a$, 세로로 자르는 횟수를 $b$라고 하자.

그럼 가로로는 $a+1$개의 조각, 세로로는 $b+1$개의 조각으로 잘리므로 총 개수는 $(a+1)(b+1)$이다.

 

 

 

 

(3+1) X (2+1) = 12개의 조각이다.

 

 

 

그런데 $a+b=n$이므로 $b=n-a$, 따라서 총 개수는 $(a+1)(n-a+1)$이다. 이 식을 전개하면 이 값은 a에 대해 아래로 볼록한 이차함수의 형태가 되고 우리는 이 $a$에 대한 이차함수와 $y=k$와의 교점이 있는지 구하면 된다. 이차함수는 축을 기준으로 대칭이므로 0~$N$이 아닌 0~$N/2$ 사이의 구간만 탐색해도 된다.(탐색 범위가 0~$N$이여도 크게 상관은 없다.

 

 

 

 

#include <bits/stdc++.h>
 
using namespace std;
 
long long n, k;
 
int main()
{
    scanf("%lld %lld", &n, &k);
    long long s=0, e=n/2+1; //e=n이여도 크게 상관 없다.
 
    while(s<=e){
        long long mid=s + e >> 1;
        long long res=(mid+1)*(n-mid+1);
        if(res==k){
            printf("YES\n");
            return 0;
        }
        else{
            if(s==e) break;
            if(res>k) e=mid-1;
            else s=mid+1;
        }
    }
    printf("NO\n");
    return 0;
}

 

 

 

 

 

두 번째 방법으로 식 $(a+1)(n-a+1)$를 전개하면 $-a^{2}+na+n+1$이 되고 $-a^{2}+na+n+1 = k$에서  근의 공식을 이용해서 $a$가 양의 정수근을 가지는지 여부를 따지면 된다.

 

 

 

#include <iostream>
#include <cmath>
 
using namespace std;
 
typedef long long ll;
 
int main()
{
    long double n, m;
    scanf("%lf %lf", &n, &m);
    long double sq=sqrt(n*n+4*(n-m+1));
    //근의 공식에서 √(b^2-4ac)가 정수인지 판별
    if(sq!=(ll)sq){
        printf("NO\n");
        return 0;
    }
    //두 근을 확인
    long double x=(n+sq)/2.0;
    if(x==(ll)x && x>0){
        printf("YES\n");
    }
    else if(1){
        x=(n-sq)/2.0;
        if(x==(ll)x && x>0){
            printf("YES\n");
        }
    }
    else{
        printf("NO\n");
    }
    return 0;
}