백준 1111. IQ Test(C++)

1111. IQ Test

1111번: IQ Test

---

입력

• 첫째 줄에 N이 주어진다. 둘째 줄에는 N개의 수가 주어진다.
• 이 수는 모두 절댓값이 100보다 작거나 같은 정수이다.

---

문제 풀이

• 규칙을 도출해서 풀이를 해야하는 문제다.
• 주어진 수열을 분석해보면 계차수열이 등비수열을 이룬다는 것을 알 수있다.
• 여기서 계차란 수열의 뒤 항에서 앞의 항을 뺀 수를 말한다.
• 따라서 계차수열이란 위와 같은 계차로 이루어진 수열이다
• 위와 같은 수열의 특징을 이용하여 계차수열의 공비만 알아낸다면 다음 항을 도출할 수 있다.
• 코드는 아래와 같다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, d, result;
vector<int>arr;
vector<int>diff;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		arr.push_back(tmp);
	}

	if (N == 1) {
		cout << "A";
	}
	else if (N == 2) {
		if (arr[0] == arr[1]) {
			cout << arr[0];
		}
		else {
			cout << "A";
		}
	}
	else {
		int d1 = arr[1] - arr[0];
		int d2 = arr[2] - arr[1];
		if (d1 == 0) {
			if (d2 != 0) {
				cout << "B";
			}
			else {
				int flag = 0;
				for (int i = 3; i<int(arr.size()); i++) {
					int tmp = arr[i] - arr[i - 1];
					if (tmp != 0) {
						flag = 1;
						break;
					}
				}
				if (flag == 1) {
					cout << "B";
				}
				else {
					cout << arr[0];
				}
			}
		}
		else {
			if (d2 % d1 != 0) {
				cout << "B";
			}
			else {
				int r = d2 / d1;
				int flag = 0;
				diff.push_back(d1);
				diff.push_back(d2);
				for (int i = 3; i<int(arr.size()); i++) {
					int tmp = arr[i] - arr[i - 1];
					if (tmp != d2 * r) {
						flag = 1;
						break;
					}
					diff.push_back(tmp);
					d2 = tmp;
				}
				if (flag == 1) {
					cout << "B";
				}
				else {
					cout << arr[N - 1] + diff[N - 2] * r;
				}
			}
			
		}
	}
	return 0;
}