BOJ 1111 - IQ Test

우선 ax+b꼴을 예측하기 위해선 적어도 세 개의 숫자가 필요하다. 따라서 N이 1일 때와 N이 2일 때를 따로 처리해주자.

1. N = 1

무조건 답은 'A'다. 다음 숫자를 예측할 (a,b) 짝이 너무 많다.

2. N = 2

만약 두 숫자가 같다면 다음 숫자도 같은 숫자가 된다.

만약 다르다면 (a,b) 짝이 너무 많아서 'A'가 답이 된다.

3. N > 2

ax+b 꼴을 예측하기 위해 첫 세 숫자에 대해 a와 b를 fix 시킨다.

그 다음 그 fixed a,b를 가지고 모든 연속된 두 숫자에 대해 만족하는지 알아보기만 하면 된다.

수열에서 첫 숫자가 x라면 두 번째 수가 y, 다시금 두 번째 수가 x로서 feedback되므로 이 구조를 눈여겨 보자.

ax+b가 모든 연속된 두 숫자에 대해 만족하기 위해선 한 직선에 있어야 한다는 점도 알아야 한다.

x = M[1]-M[0] // x로서의 두 수의 차이

y = M[2]-M[1] // y로서의 두 수의 차이

a = y/x   // a는 기울기

b = M[1] - a*M[0]    // 단순 y 절편, (M[0],M[1])을 ax+b=y에 대입한다.

#include <cstdio>

int main() {
	int N, M[51], i, b, F = 1, x, y, a;
	scanf("%d", &N);
	for (i = 0; i < N; i++)
		scanf("%d", &M[i]);

	if (N == 1) printf("A");
	else if (N == 2) {
		if (M[0] == M[1]) printf("%d",M[0]);
		else printf("A");
	}
	else {
		a = 0;
		x = M[1] - M[0];
		y = M[2] - M[1];
		if (x != 0) a = y / x;
		b = M[1] - a*M[0];
		for (i = 1; i < N; i++) {
			if (M[i] != (M[i - 1] * a + b)) {
				F = 0;
				break;
			}
		}
		if (F) printf("%d", (M[N - 1] * a + b));
		else printf("B");
	}

	return 0;
}