(C++) 백준 1111번 IQ Test

맨 처음에 DivisionByZero라는 런타임 에러가 떴다.  0으로 나눈 것이 없다고 생각했는데

자세히 보니  어디에서 런타임 에러가 뜨는지 확인했고, 빠르게 고쳐서 성공했다.

 

시간제한이 2초이다. 2초를 보고 오래 걸리는 문제인 거 같아서 바로 for문으로 푸는 방법을 생각해봤다. 

부르트 포스처럼 하나하나 다 대입해서 모든 수를 만족하는 함수를 만드고 함수의 개수가 2개 이상이면 B 그렇지 않으면,

내가 만든 함수에 넣는 코드를 짜서 시간복잡도를 계산해보니 8억(8초)이 나오는 것을 확인했다.

다시 마음을 가다듬고  for 문을 푸는 문제가 아님을 직감하고, 어떻게 하면, 풀 수 있을지 고민했다. 

일단 case를 나누어봤다.

N의 수에 따른 case를 나누어 보겠다.

 

N=1

무조건 A출력 답이 2개 이상이다.

 

N=2

arr[0] == arr [1] ==> arr [0] 또는 arr [1]을 출력한다. ex) 57 57a는 1b는 0  or a는 0b는 57 무조건 다음수는 57

arr [0]!= arr [1]  ==> A출력 답이 2개 이상이다..

 

N=3

 

n이 3이상부터는 일차 함수/상수 함수를 구할 수 있는 조건이 된다.

그러면 a(기울기를 구하는 방법에 대해서 이야기를 해보자)

y=ax+b

y=ax'+b

두식을 빼주면 ax'-ax = a(x'-x)만 남는다. 그러면 b의 값에 상관없이 기울기에 상수를 곱한 값이 나온다.

이 식을 두개 이상 만들어 줄 수 있다면, 그때부터 기울기를 구할 수 있다. 

그 예로

a = (iq[2] - iq [1]) / (iq [1] - iq [0]); 

 

a(기울기)를 구했으면 b는 자동완성이라고 봐도 무방하다. 

 

b = iq[1] - iq [0] * a; 

 

이렇게 하면 더 이상의 문제는 없다. 

그리고 각종 예제의 예외를 걸러주는 조건문을 걸어주면 에러도 안 뜨고 성공이 뜨게 된다. 

#include <iostream>
#include <algorithm>
#include <vector>
#pragma warning(disable:4996)
using namespace std;
int arr_a[201] = { 0, };
int arr_b[201] = { 0, };
int a;
int b;

int main() {
	
	int t;
	cin >> t;	vector <int> iq(t);
	for (int i = 0; i < t; i++) {
		cin>>iq[i];
	}
	if (t == 1) {
		cout << "A";
		return 0;

	}
	if (t == 2) {
		if (iq[0] == iq[1]) {
			cout << iq[0];
			return 0;
		}
		if (iq[0] != iq[1]) {
			cout << "A";
			return 0;
		}
	}
	if (t >= 3) {
		if (((iq[2] - iq[1]) == 0) && ((iq[1] - iq[0]) == 0) || (iq[1] - iq[0])==0) {
			
			b = iq[1];
			for (int i = 2; i < t; i++) {
				if (iq[i] != b) {
					cout << "B";
					return 0;
				}

			}
			cout <<  b;
			return 0;

		}
		if ((iq[2] - iq[1]) % (iq[1] - iq[0]) ) {
			cout << "B";
			return 0;
		}
		else {
			a = (iq[2] - iq[1]) / (iq[1] - iq[0]);
			b = iq[1] - iq[0] * a;
		}
		for (int i = 2; i < t; i++) {
			if (iq[i] != iq[i-1] * a + b) {
				cout << "B";
				return 0;
			}
		}
		cout << iq[t - 1] * a + b;
		return 0;

	}



}