🔍 1111 IQ Test

IQ Test의 문제 중에는 공통된 패턴을 찾는 문제가 있다. 수열이 주어졌을 때, 다음 수를 찾는 문제이다.

예를 들어, 1, 2, 3, 4, 5가 주어졌다. 다음 수는 무엇인가? 당연히 답은 6이다. 약간 더 어려운 문제를 보면, 3, 6, 12, 24, 48이 주어졌을 때, 다음 수는 무엇인가? 역시 답은 96이다.

이제 제일 어려운 문제를 보자.

1, 4, 13, 40이 주어졌을 때, 다음 수는 무엇일까? 답은 121이다. 그 이유는 항상 다음 수는 앞 수*3+1이기 때문이다.

은진이는 위의 3문제를 모두 풀지 못했으므로, 자동으로 풀어주는 프로그램을 작성하기로 했다. 항상 모든 답은 구하는 규칙은 앞 수*a + b이다. 그리고, a와 b는 정수이다.

수 N개가 주어졌을 때, 규칙에 맞는 다음 수를 구하는 프로그램을 작성하시오.

---

🤔 풀이

• 처음 풀이
  '음... b는 나열된 두 숫자의 차이를 넘지 않을거고..!(아님, a가 음수면 가능함) a는 그 전의 숫자를 곱해주는거니까 b보다 작겠지...(이것도 아님. b가 음수일수도 있음)' 아무튼 이런 틀린 생각을 가지고 다음과 같이 풀었다.

/* 1. 두 숫자를 나눈다. 나눠서 나온 몫 이하로 a를 기준으로 다 돌려보기.
	1-1. N2를 N1로 나눈다. => 값 : p.rr...
	1-2. 값 p를 a로 세운다.
	1-2-1. N1에 a를 곱해 N2의 차를 벡터에 저장한다.
	1-3. a = a-1; 해서, -p까지 한다. <p가 마이너스일 때를 고려하지 않음. 추가로 r도 마이너스가 될 수 있다...>

	2. 다음 두 숫자로 넘어간다.
	2-1. 벡터에서 숫자를 꺼내서 그 식이 성립하는지 확인한다. 아니면 컷. 마지막까지 반복.

	3. 벡터에 남은값을 확인한다. 만약에 하나만 남아있으면, 다음 수 계산 ㄱㄴ 출력.
	만약, 여러개가 남아있으면 A를 출력.
	하나도 없다면, B를 출력.
*/

• (N이 3 미만일 때)
  - 주어진 숫자가 하나밖에 없다면 규칙을 여러개 세울 수 있다. 따라서 답이 여러개임을 출력한다. \
  - 주어진 숫자가 두개뿐이라면, 두 가지 케이스로 나눌 수 있다.
  1) 만약 두 숫자가 같을 때는 a가 1이고, b가 0이거나 a가 0이고 b가 숫자 자체이다. 두 경우 모두 구할 수 있는 다음 수는 같으므로, 해당 수를 출력한다.
  2) 만약 두 숫자가 다를 때는 두 숫자만으로는 하나의 규칙을 찾을 수 없다. 따라서 답이 여러개임을 출력한다.
• (N이 3 이상일 때)
  문제의 규칙을 보면 $\begin{cases} N_2 = N_1\times a + b \cdots(1) \\ N_3 = N_2\times a + b\cdots(2) \\ \dots \end{cases}$ 을 따른다는 것을 알 수 있다.
  - (1)번 식과 (2)번 식을 연립하면 $N_3 - N_2 = a\times (N_2-N_1) \Rightarrow a = (N_3-N_2)/(N_2-N_1)$ 이 나온다. 문제에서 a가 정수라고 하였으므로, 두 식을 연립해서 구한 a가 정수가 아닐 경우에는 답을 구할 수 없다. 만약 구한 a가 정수라면 b 또한 구할 수 있다. (추가적으로 $N_2-N_1$이 0일일수도 있다. zeroDivision을 방지하기 위해 이때는 a가 0인것으로 계산한다)
  - $N_1, N_2, N_3$ 을 연립해서 구한 a, b 이므로 다른 숫자에서는 적용되지 않을 수 있다. 따라서 입력받은 숫자들을 구한 a, b로 계산한 값과 같은지 비교하여 모두 같으면 다음 수를 구하여 출력하고, 다르다면 구할 수 없음을 출력한다.

---

📝 코드

#include <iostream>
using namespace std;

int N;
int list[50];

int main() {
    /** INPUT **/
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
    /** SOLUTION **/
    int a, b;
    if (N <= 2) {
        if (N == 1) {
            // 값이 여러개임. A
            cout << 'A';
        }
        else {
            if (list[0] == list[1]) {
                // a가 1이고, b가 0인 것.
                cout << list[0];
            }
            else {
                // 값이 여러개임. A.
                cout << 'A';
            }
        }
        return 0;
    }
    else {
        int inter1 = list[1] - list[0];
        int inter2 = list[2] - list[1];
        if (inter1 == 0) {
            a = 0;
        }
        else {
            if (inter2 % inter1 != 0) {
                cout << 'B';
                return 0;
            }
            a = inter2 / inter1;
        }
        b = list[1] - a*list[0];
    }

    for (int idx = 1; idx < N; idx++) {
        if (list[idx] != list[idx-1]*a + b) {
            cout << 'B';
            return 0;
        }
    }

    cout << list[N-1]*a + b;
    return 0;
}