[Math] BOJ 1111 IQ Test

문제 링크 : www.acmicpc.net/problem/1111

1111번: IQ Test

정답인 a, b에 대해 제시된 수열은 항상 X(i+1) = a * Xi + b를 만족한다. 즉, 이는 일반항이다.

우리는 제시된 수열의 길이에 따라 Case를 구분할 수 있다.

 

① 제시된 수열의 길이가 1일 때

우리는 a, b를 특정할 수 없다. 다음 수가 아예 없기 때문이다.

이 경우 정답은 A이다.

 

② 제시된 수열의 길이가 2일 때

두 가지 경우로 나뉜다.

제시된 수를 29, 38이라 해보자. 이 때, a = 1, b = 9로 두었을 경우 a, b는 식을 만족시킨다. (38 = 29 * 1 + 9)

하지만 (a = 2, b = -20), (a = 3, b = -49) 등 가능한 순서쌍은 무한히 많다. 따라서 이 때 정답은 A이다.

하지만 제시된 수가 3, 3일 때를 살펴보자. (a = 1, b = 0), (a = 2, b = -3) 등 어떠한 순서쌍을 적용해도 결과는 항상 같다. 즉, (a, b)의 순서쌍은 무한히 많지만 결과는 동일한 값이 나오므로, 이 경우 정답은 수열의 첫번째 수와 같다.

 

③ 제시된 수열의 길이가 3 이상일 때

이제 우리는 3개 이상의 항을 통해 다음 식을 세울 수 있다.

수열의 일반항에 의해 X(i+2) = a * X(i+1) + b 이고, X(i+1) = a * Xi + b 이다.

따라서, X(i+2) - X(i+1) = a(X(i+1) - Xi) 이다.

이 식을 통해 b도 구할 수 있다. b = X(i+1) - a * Xi

즉 이 경우 a, b는 순서쌍 하나로만 나타나게 되므로, 제시된 모든 수열에 대해 a, b를 통해 세운 식을 만족하는지 확인하면 된다.

만족한다면 마지막 수에 대한 결과를, 그렇지 않다면 B를 출력한다.

 

※ 단, a를 구하는 식에서 X(i+1) = Xi일 수 있다. 이 경우에는 ②와 마찬가지로 수열의 모든 수가 수열의 첫 번째 수와 같아야 함에 유의한다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <memory.h>
 
using namespace std;
typedef long long ll;
typedef pair<int, int> p;
 
int n, seq[50];
 
void get_answer() {
    //예외 : 처음 두 수가 같은 경우, 반드시 세 번째 항도 같아야 함
    if (seq[0] == seq[1]) {
        for (int i = 2; i < n; i++) {
            if (seq[i] != seq[0]) {
                printf("B\n");
                return;
            }
        }
        printf("%d\n", seq[0]);
        return;
    }
 
    //첫 번째 수에 대해, 가능한 a, b의 쌍을 구한다.
    int a = (seq[2] - seq[1]) / (seq[1] - seq[0]);
    int b = seq[2] - (seq[1] * a);
 
    //나머지 수들에 대해 확인하기
    for (int i = 0; i < n - 1; i++) {
        if (seq[i] * a + b != seq[i + 1]) {
            printf("B\n");
            return;
        }
    }
 
    printf("%d\n", seq[n - 1] * a + b);
}
 
void init() {
    cin >> n;
 
    for (int i = 0; i < n; i++) cin >> seq[i];
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    if (n == 1) { printf("A\n"); return 0; }
    if (n == 2) {
        if (seq[0] == seq[1]) printf("%d\n", seq[0]);
        else printf("A\n");
        return 0;
    }
    get_answer();
 
    //system("PAUSE");
    return 0;
}