백준 #1111 IQ Test

이번 문제는 이원 일차 방정식을 푸는 문제입니다.  IQ Test란 이름을 가지고 있지만, 뭐 그렇게 거창한 것은 아닙니다.

이원 일차 방정식에서 미지수를 구하기 위해서는 최소 2개의 식이 필요합니다.  Gold III 문제인데, 정답률은 15.4%로 아주 낮습니다.  실제 문제 난이도가 어려운 것은 아닌데, 틀릴 수 있는 소지가 많아서 난이도가 높게 잡혔다고 보입니다.

 

 

이월 일차 방정식

이원일차 방정식으로 풀어도 되겠지만, 인접한 두 항의 차를 구하는 방법도 있습니다.  앞에 방식보다는 인접한 두 항의 차를 이용하는 것이 더 편하겠죠.  사실 원리는 이원일차 방정식에서와 똑같습니다.

 

\[ ax_0 + b = x_1 , ax_1 + b = x_2 \to a( x_1 - x_0 ) = x_2 - x_1 \]

 

일단 처음 3개의 항만 있어도, a, b 값을 결정할 수 있습니다.  그런데 두 항의 차이를 계산해서 두개의 값을 구했는데, 한쪽이 0인 값이 되면, a 값을 결정하지 못 하거나, 존재하지 않을 수가 있습니다.  이것에 대해서 적절하게 처리해주어야 합니다.  그런데 a를 결정할 수 없는 경우는 a = 1, b = 0 으로 결정해도 상관이 없습니다.

 

두번째 경우는 a 값이 분수가 되는 경우입니다.  문제에서 a 값은 정수라고 규정되어 있으니, 이 경우에는 불능으로 처리해주면 됩니다.

 

간단하게 틀릴 수 있는 예제를 올려놓습니다.

 

1
3

Result
A

2
1 1

Result
1

2
1 2

Result
A

3
8 12 18

Result
B

 

예외 처리만 잘 해주면 어렵지 않은 문제입니다.

제가 짠 소스입니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------------------------------------
//  baekjoon #1111 - IQ Test
//    - by Aubrey Choi
//    - created at 2019-08-31
//----------------------------------------------------------------------------------
#include <stdio.h>

//  x2 = ax1 + b, x3 = ax2 + b -> (x3-x2) = a(x2-x1)
int main()
{
  int n, a, b, v[50], i;
  scanf("%d",&n);
  for(i=0;i<n;i++) scanf("%d",v+i);
  if(n==1 || (n==2&&v[0]!=v[1])) { puts("A"); return 0; }
  if(n==2) { printf("%d\n", v[0]); return 0; }
  if(v[0]==v[1])
  {
    if(v[1]!=v[2]) { puts("B"); return 0; }
    a = 1, b = 0;
  }
  else
  {
    if((v[2]-v[1])%(v[1]-v[0])) { puts("B"); return 0; }
    a = (v[2]-v[1])/(v[1]-v[0]);
    b = v[1]-a*v[0];
  }
  for(i=3;i<n;i++) if(v[i]!=a*v[i-1]+b) break;
  if(i<n) puts("B"); else printf("%d\n", a*v[n-1]+b);
  return 0;
}