점( BOJ 2541 )

문제 : https://www.acmicpc.net/problem/2541

2541번: 점

 

문제 파악하기

시작점 (a, b)에서 3가지 규칙을 사용하여 집합 S에 점을 추가할 때, 주어진 (x, y)가 집합 S에 포함될 수 있는지 여부를 확인하는 문제입니다. 입력되는 점의 범위는 1 ~ 100,000이기 때문에 단순히 모든 경우의 수를 파악할 수는 없습니다. 대신 규칙을 계속 적용할 때 나타나는 특징을 살펴보면 문제를 해결할 수 있습니다.

 

문제 해결하기

규칙 3가지를 적절하게 이용하면 우리는 항상 점 (a, b)의 a 와 b 중 하나 이상의 좌표값이 1인 점을 추가할 수 있습니다. 이는 (a, b)가 모두 짝수라면 규칙 3을 사용해서 나누어주고, 만약 나눌 수 없다면 규칙 1과 규칙 2를 사용해 짝수로 만들어주어 계속 나누는 알고리즘을 사용하면 됩니다. 예를 들어, 점 (5, 8)이 있다고 가정해보면 다음과 같은 과정을 통해 점 (1, 4)을 추가할 수 있습니다.

 

(5, 8) > (6, 9) > (6, 9) +(9, 12) = (6, 12) > (3, 6) > (4, 7) + (7, 10) = (4, 10) > (2, 5) > (2, 5) + (5, 8) = (2, 8) > (1, 4)

 

이렇게 모든 좌표를 항상 짝수로 만들어주면서 2로 계속 나누어주면 (a, b)의 a와 b 중 하나 이상의 좌표값이 1인 상태가 되며, 이 점이 우리가 추가할 수 있는 가장 작은 점의 좌표라고 할 수 있습니다.

 

이렇게 (a, b)를 사용하여 집합 S에 추가할 수 있는 가장 작은 점의 좌표를 구했다면 남은 일은 (x, y)를 추가할 수 있는지 여부를 파악하는 것입니다. 가능 여부를 확인할 때에 중점으로 확인할 값은 a와 b의 차이값(d)과 x와 y의 차이값(dd)입니다. 집합 S에 추가할 수 있는지 여부는 dd가 d의 배수인지에 여부에 따라 달라지게 됩니다. 만약 dd가 d의 배수라면, 즉 x와 y의 차이값(dd)이 a와 b의 차이값(d)의 배수라면 항상 (x, y)를 만들 수 있습니다. 이는 규칙 2번을 활용하면 쉽게 확인할 수 있습니다. 규칙 2번을 사용하면 a와 b의 차이값인 d가 배수만큼 증가하기 때문입니다. 그렇기에 반대로 dd가 d의 배수가 아니라면 (x, y)는 절대 만들 수 없습니다. 이렇게 d와 dd의 값을 통해 5개의 점을 확인하면 문제를 해결할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
 
int a, b, x, y;
int d, dd;
 
int abs(int k) { return k>=0 ? k:-k; }
 
int main() {
    scanf("%d %d", &a, &b);
    d = abs(b-a);
 
    // (a, b)가 될 수 있는 가장 작은 숫자로 변환
    if(a == b) a = b = 1;
    else {
        while(d%2 == 0) d /= 2;
 
        if(a < b) {
            a = 1;
            b = 1+d;
        }
        else {
            a = 1+d;
            b = 1;
        }
    }
 
    for(int i=1;i<=5;i++) {
        scanf("%d %d", &x, &y);
 
        if((a<=b) != (x<=y)) printf("N\n");
        else {
            dd = abs(y-x);
 
            if(d*dd == 0) {
                if(d == dd) printf("Y\n");
                else printf("N\n");
            }
            else {
                // dd%d == 0 이라면 숫자들을 조합해서 (x,y)를 만들 수 있음
                if(dd%d == 0) printf("Y\n");
                else printf("N\n");
            }
        }
    }
}

후기

정올 1번에 어울리는 문제라고 생각합니다. 규칙들을 분석한 다음, 특징을 통해 복잡한 계산 없이 간단한 조건문으로 풀 수 있기에 정올을 처음 준비하는 사람들에게 소개할만한 문제라고 생각합니다.