백준 1111. IQ Test

https://www.acmicpc.net/problem/1111

1111번: IQ Test

 

처음에 브루트포스로 a,b 를 구하려고 했는데 a,b의 최소 최대를 알 방법이 없고 돌아가는 시간도 오래 걸릴것 같아서 다른 방법을 생각해봤다.

 

우선 N==1인 경우는 당연히 다음에 뭐든 올수 있기 때문에 "A"이다.

 

N==2인 경우는 만약 첫번째 숫자 x1과 두 번째 숫자 x2가 같다면 다음 숫자도 같은 숫자일수 밖에 없을 것이다.

하지만 두 숫자가 다르다면 세 번째 숫자는 어떤 숫자든 올수 있다.

 

N >= 3인 경우가 문젠데 여기서 부터는 숫자가 3개 이상 주어지므로 연립방정식으로 a와 b를 구할수 있다.

연립방정식은 다음과 같다. 

 

X1A + B = X2 

X2A + B = X3 

 

연립방정식을 풀어서 A,B를 구할수 있는데 계산할때 주의해야 한다.

풀어보면 A = (X2-X3) / (X1-X2) 가 나오기 때문에 (X1-X2) == 0 이면 즉 X1== X2면 0으로 나눠지게 되므로 에러가 난다. 

따라서 X1==X2인 경우에는 A=0,B=X1 로 예외 처리해줘야 한다.