백준 1111번 IQ Test 문제풀이 c++

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

1111번: IQ Test

문제해석

예를 들어 N=4인 수열 K1 K2 K3 K4가 주어졌을때

aK1+b=K2

aK2+b=K3

aK3+b=K4

를 만족하는 정수 a와 b를 구한 후 aK4+b를 출력하고 위 조건을 만족하는 정수 a, 정수 b가 없을경우 B를 aK4+b값이 둘이상의 값을 가지면 A를 출력하면 되는 문제이다.

 

일단 N=1일때는 다음으로 가질수있는 값이 여러개이므로 무조건 A를 출력한다.

 

N=2일때는 두 숫자가 같으면 다음 값도 두 숫자와 같은 숫자 단 하나로 결정되고

두 숫자가 다르다면 다음 값이 두개 이상의 값을 가질수 있으므로 A를 출력한다.

 

N이 3이상일때부터 설명하자면

arr[0]=K0,arr[1]=K1,arr[2]=K2,arr[3]=K3 , ........., arr[n]=Kn가 있다고 가정하면

인접한 두 수의 차이 K1-K0 , K2-K1 , K3-K2 ,....., Kn-kn-1 을 유심히 살펴보면

a(K1-K0)=K2-k1

a(K2-K1)=K3-k2

a(K3-K2)=K4-k3

......

a(Kn-1-Kn-2)=Kn-kn-1

이 됨을 찾을 수가 있다.

 

왜냐하면

aK0+b=K1

aK1+b=K2

에서 아래식에서 윗 식을빼면 

a(K1-K0)=K2-k1 이 식이 나오고

aK2+b=K3

aK3+b=K4

이것도 아래식에서 윗 식을빼면

a(K2-K1)=K3-k2 이렇게 나온다.

 

이렇게 인접한 두 수의 차이를 벡터 v에 넣어주게되면 벡터의 앞 원소부터 공비가 a인 등비 수열을 이루게 된다.

그렇다면 v[1]/v[0] 즉 a가 정수인가 정수가 아닌가 두가지 케이스를 따져야한다.

정수가 아니라면 B를 출력해야한다.

코드 부분의 if(a!=round(a))이 부분이 a가 정수인가를 판별하는 부분이 된다.

정수인경우에는 벡터의 끝까지 v[i+1]/v[i]가 a와 같은지 확인해야한다.

하나라도 v[i+1]/v[i] 이값이 같지 않을경우 B를 출력해야한다.

모든 v[i+1]/v[i]가 a와 같았다면 괜찮은 것이다.

 

드디어 숫자를 출력 할 수있는 기회가 온것 a는 이미 구했고 arr[0]과 arr[1]를 통해 b도 구할 수 있으므로 

a*arr[n-1]+b를 출력 하면 된다.

여기까지 일반적인 모든 경우를 출력 할 수있다.

 

아직 예외 처리를 하지않은 부분이 있는데 먼저 v[1]/v[0]에서 v[0]가 0일때이다.

v[0]이 0이고 v[1]이 0이 아닌경우 이건 말이 안된다.

예를들어 arr가 3 3 5 같은 경우이다 3a+b=3이면서 3a+b=5인경우는 없기때문에 B를 출력해야한다.

 

두번째는 v[0]이 0이고 v[1]이 0인경우이다.

arr가 3 3 3 같은 경우이다. 이때는 arr[0]에서 끝까지 같은지 확인해야한다 코드 부분의 check2()함수이다.

 

마지막으로 v[i+1]/v[i]를 확인할때이다.

4

1 0 0 0 같은 입력이 주어지면

v벡터에는 -1 0 0 이 들어가있는데 이때 0/0이 발생한다.

위에서 v[i+1]/v[i]가 a랑 같으면 괜찮았다고 했는데  v[i+1]이 0이고 v[i]이 0일때역시 괜찮다고 처리해주면 된다.

이 부분이 좀 헷갈려서 혼자 이해는 했는데 설명을 하려니 어떻게 설명해야할지 잘모르겠다...

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
vector <double> v;
int check();
bool check2();
double arr[50];
int n;
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>arr[i];
    }
    if(n==1)
    {
        cout<<"A\n";
    }
    else if(n==2)
    {
        if(arr[0]==arr[1])
        {
            cout<<arr[0]<<"\n";
        }
        else
        {
            cout<<"A\n";
        }
    }
    else
    {
        for(int i=0; i<=n-2; i++)
        {
            v.push_back(arr[i+1]-arr[i]);
        }
        if(check()==1)
        {
            double a=v[1]/v[0];
            double b=arr[1]-a*arr[0];
            cout<<arr[n-1]*a+b<<"\n";
        }
        else if(check()==2)
        {
            if(check2()==true)
            {
                cout<<arr[0]<<"\n";
            }
            else
            {
                cout<<"B\n";
            }
        }
        else if(check()==0)
        {
            cout<<"B\n";
        }
    }
    return 0;
}
bool check2(){
    for(int i=0; i<=n-2; i++)
    {
        if(arr[i]==arr[i+1])
        {
            continue;
        }
        else
        {
            return false;
        }
    }
    return true;
}
int check(){
    if(v[0]==0&&v[1]==0)
    {
        return 2;
    }
    else if(v[0]==0&&v[1]!=0)
    {
        return 0;
    }
    else
    {
        double a=v[1]/v[0];
        if(a!=round(a))
        {
            return 0;
        }
        else
        {
            for(int i=1; i<=v.size()-2; i++)
            {
                if(a==v[i+1]/v[i]||(v[i+1]==0&&v[i]==0))
                {
                    continue;
                }
                else
                {
                    return 0;
                }
            }
        }
        return 1;
    }
}

 

0으로 나누는 부분의 예외 처리가 까다로웠음