[백준] 1111 IQ Test

문제 주소 : www.acmicpc.net/problem/1111

1111번: IQ Test

문제 확인

 

브루트 포스 혹은 수학으로 풀 수 있는 문제입니다.

 

풀이

 

브루트 포스를 통해 ax + b 식을 구해 풀 수 있지만 느리므로 계산식을 이용해 풀었습니다.

 

n = 1의 경우 뒤에 어떠한 숫자가 올 수 있으므로 A

 

n = 2의 경우 x1 = x2 일 때 나올 수 있는 식은 y = x + 0, y = -x + 2 * x1로 2가지가 나옵니다. 하지만 x1 = x2 이므로 두 식의 결과는 항상 일정한 x1 값이 나오므로 x1을 출력합니다.

그 외의 경우는 나올 수 있는 값이 많으므로 A를 출력합니다.

 

n>2 인 경우 x1, x2, x3의 관계식을 통해 구합니다. 식은 항상 ax + b 1차식 형태를 가지므로 (x1, x2), (x2, x3)로 두어 기울기 a를 구한 후 b값을 (x1, x2) 값을 대입하여 구합니다.

a, b는 정수이므로 기울기 값이 정수가 아니라면 (x2, x3) 대입 시 틀린 값이 나오게 됩니다.

계속해서 입력 받은 값을 대입하여 검증하고 틀리면 B, 마지막까지 맞다면 a*x + b 값을 출력합니다.

 

코드

#include <cstdio>
#include <vector>
 
using namespace std;
 
int main() {
    int n;
    scanf("%d", &n);
    if (n > 2) {
        int x, y, z, a, b;
        scanf("%d%d%d", &x, &y, &z);
        a = y-x ? (z - y) / (y - x) : 0;
        b = y - x * a;
        if (y*a + b != z) { printf("B"); return 0; }
        for (int i = 3; i < n; i++) {
            y = z;
            scanf("%d", &z);
            if (y*a + b != z) { printf("B"); return 0; }
        }
        printf("%d", z*a + b);
    }
    else if (n == 2) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (x == y)
            printf("%d", x);
        else
            printf("A");
    }
    else
        printf("A");
}