[도전 9일차] 2541 점

※복습 : 

문제 : BOJ 2541 점

문제 링크

KOI 2007 고등부 1번

 

사용 알고리즘 : 수학

 

아이디어 제공 : hongjun님의 블로그

풀이: 

초기에 점 (x,y)가 주어진다.

(규칙 1) 점 (x, y)가 S에 속해 있다면,  점 (x+1, y+1)을 S에 추가한다. 
(규칙 2) 점 (x, y)가 S에 속해 있고, x와 y가 모두 짝수이면, 점 (x/2, y/2)를 S에 추가한다.
(규칙 3) 두 점 (x, y)와 (y, z)가 S에 속해 있다면, 점 (x, z)를 S에 추가한다.

그 후 주어지는 5개의 점에 대해 S에 속할 수 있는지 판별하는 문제다.

단순하게 생각해도 x,y의 범위가 1~10^5이므로 백트래킹과 같은 방법은 시간 제한안에 수행되지 못한다.

 

규칙을 분석하여 가능한 점들의 특징을 알아보자.

 

1. 초기 x,y 간 대소 관계가 유지된다. 

 

2. 일반성을 잃지 않고 x<y, y=x+d 라 하자.

이때 초기값으로부터 만들어질 수 있는 점들은 다음과 같다.

(x, x+d) -[by 규칙 1]-> ( x+d, x+2d) -[by 규칙 3]-> (x, x+2d) -[같은 방법으로]-> (x, x+nd)

(x,x+nd) -[by 규칙 1] -> a>=x인 임의의 a에 대해 (a,a+nd)

 

3. x<=2^k 에 대해 a=2^k, n=2^k 로 두자.  (2^k , 2^k + (2^k) *d ) 가 가능하고

규칙 2에 의해 (1, 1+d) 가 가능하다. 
같은 방법으로 d = (2^k) * m (m은 홀수, k>=0인 정수) 로 나타냈을 때

(1,1+(2^k) *m ) => (2^k,2^k + (2^k)*m) => (1,1+m) 

 

즉, d의 가장 큰 홀수인 소인수 m에 대하여 y-x 가 m의 배수인 모든 (x,y)가 가능하다. (단,x,y간 대소 유지)

만약 d=0이면 a>=0인 모든 a에 대하여 (a,a)가 가능하다. 

 

결론을 코드로 구현하면 된다.

코드

//pentagon@sasa.hs.kr 
#include<bits/stdc++.h>
using namespace std;
int x,y;
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>x>>y;
    int flag;
    if(x==y) flag=0;
    else if(x>y) flag=1;
    else flag=-1;
    int d = abs(x-y);
    while(d>0 && d%2==0) d/=2;
    for(int i=0;i<5;i++){
        cin>>x>>y;
        int f=0;
        if(flag==0 && x==y)
            f=1;
        else if(flag*(x-y)>0 && abs(x-y)%d==0)
            f=1;
        cout<<(f?'Y':'N')<<'\n';
    }
}