백준 1111 / C++

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

1111번: IQ Test

 

수열이 규칙성을 만족하는지 확인하고 유일하면 출력까지 하는 문제이다. 

일단 규칙이 p*전항+q 이므로 미지수가 2개이다. 

따라서 a1, a2, a3만으로 p와 q는 결정된다. (항이 3개 이상일때)

 

// 항이 3개 이상 

p=(a3-a2)/(a2-a1)이 된다. p가 정수면, q도 정수이므로 a3-a2가 a2-a1의 배수인지만 체크해주자. (예외처리는 a1=a2일때)

이렇게 해서 정수 p, q를 찾았다. 이제 수열을 1번 돌면서 모두 이 규칙인지 확인한다. 

잘 가다가 이상하게 바뀌면 규칙성이 없어서 B를 출력, 끝까지 규칙을 유지하면 다음값을 출력해준다. 

 

// 항이 2개 이하

항이 1개일땐 아무거나 와도 되므로 A를 출력

항이 2개일땐 만약 a1=a2라면 계속 a1 a1 a1 ... 이므로 a1을 출력

만약 a1!=a2라면 a2=p*a1+q 에서 p,q 를 잘 조절해주면 다양하게 가능하므로 A를 출력 

 

[ 코드 ]

 

#include <bits/stdc++.h>
using namespace std;
int a[55];

void go(int n) {
    // n<=2
    if (n == 1) {
        cout << "A";
    }
    else if (n == 2) {
        if (a[1] == a[2]) {
            cout << a[1];
        }
        else {
            cout << "A";
        }
    }
    // n>=3
    else {
        // p가 정수가 아닐 때
        if (a[1]!=a[2] && (a[3] - a[2]) % (a[2] - a[1])) {
            cout << "B";
        }
        else {
            // p가 정수일 때 
            int p = a[1] == a[2] ? 0 : (a[3] - a[2]) / (a[2] - a[1]);
            int q = a[2] - p * a[1];
            // 모든 항이 규칙 만족하는지 체크 
            for (int i = 2; i <= n; i++) {
                if (a[i] != p * a[i - 1] + q) {
                    cout << "B";
                    return;
                }
            }
            cout << a[n] * p + q;
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    go(n);
}