[BOJ/Gold 3] 백준 1111 IQ Test(C++)

문제 링크

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

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개가 주어졌을 때, 규칙에 맞는 다음 수를 구하는 프로그램을 작성하시오.

입력

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

출력

다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다.

예제 입력 1

4
1 4 13 40

예제 출력 1

121

예제 입력 2

5
1 2 3 4 5

예제 출력 2

6

예제 입력 3

5
3 6 12 24 48

예제 출력 3

96

예제 입력 4

1
0

예제 출력 4

A

예제 입력 5

2
-1 2

예제 출력 5

A

예제 입력 6

2
57 57

예제 출력 6

57

예제 입력 7

4
16 -8 4 -2

예제 출력 7

B

예제 입력 8

5
6 5 4 3 1

예제 출력 8

B

예제 입력 9

4
-12 12 -36 60

예제 출력 9

-132

알고리즘 분류

• 구현
• 많은 조건 분기

풀이

1. 숫자가 1개만 주어졌을 경우에는 어떤 수가 다음에 올 지 모르므로, A를 출력한다.

2. 숫자가 2개인 경우

   - 두 수가 같다면 다음 수도 똑같으므로 똑같은 수를 출력한다.

   - 두 수가 다른 경우 어떤 수가 다음에 올 지 모르므로 A를 출력한다.

3. 숫자가 3개 이상인 경우

   - 앞의 두 수가 같은 경우

      - 3번째 이상의 수도 같은 경우 N+1번째 수도 같다.

      - 3번째 이상의 수 중에서 다른 수가 있을 경우 잘못된 입력이므로 B를 출력한다.

   - 앞의 두 수가 다른 경우, A, B가 정수가 나오는 지 안 나오는지 체크한다.

        ※ 세 수를 X, Y, Z라고 했을 경우, A = (Y - Z) / (X - Y)이다. (Y - Z) % (X - Y)가 0이면 A는 정수고, 0이 아니라면 A는 정수가 아닌 것이다. B = Y - (X * A)이다.

      - A, B가 정수라면 정해진 규칙(앞 수 * A + B == 뒷 수)대로 숫자들이 나열되었는지 체크하여, 규칙대로 나열되었다면 N+1번째 수를 계산하여 출력한다.

      - 규칙대로 나열되지 않았다면 잘못된 입력이므로 B를 출력한다.

      - A, B가 정수가 아니라면 잘못된 입력이므로 B를 출력한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 55
#define INF 1e9

using namespace std;
int N, A, B;
int MAP[MAX];
int answer = 0;

bool Calc(int X, int Y, int Z) {
	if ((Y - Z) % (X - Y) != 0) { // A가 여기서 정수로 판정된다면 B도 정수이다.
		return false;
	}
	A = (Y - Z) / (X - Y);
	B = Y - (X * A);
	return true;
}

int new_Number() {
	return ((MAP[N - 1] * A) + B);
}

int main() {
	FIRST
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> MAP[i];
	}
	if (N == 1) {
		/*
			숫자가 1개만 주어졌을 경우에는 다음 수를 알 수 없다. 무수히 많은 다음 수가 올 수 있으므로 A를 출력한다.
		*/
		cout << "A" << "\n";
	}
	else if (N == 2) { // 숫자가 2개만 주어졌을 때
		if (MAP[0] == MAP[1]) { // 두 수가 같다면 다음 수 역시 똑같을 것이다.
			cout << MAP[0] << "\n";
		}
		else { // 하지만 두 수가 다르다면 다음 수를 구할 수 없다.
			cout << "A" << "\n";
		}
	}
	else if (N >= 3) { // 숫자가 3개 이상 주어질 때
		if (MAP[0] == MAP[1]) { // 앞에 두 수가 같은데 
			bool Flag = true;
			for (int i = 0; i < N; i++) {
				if (MAP[0] != MAP[i]) {
					Flag = false;
				}
			}
			if (Flag) { // i번째 수도 같은 경우 
				cout << MAP[0] << "\n";
			}
			else { // i번째 수가 다른 경우 잘못된 입력이다.
				cout << "B" << "\n";
			}
		}
		else { // 앞의 두 수가 다른 경우
			if (Calc(MAP[0], MAP[1], MAP[2])) { // A, B가 정수가 나오는지 안 나오는지 체크
				// A, B가 정수라면
				bool Flag = true;
				for (int i = 0; i < (N - 1); i++) { // 정해진 규칙(앞 수 * A + B == 뒷 수)대로 숫자들이 나열됐는지 체크
					if ((MAP[i] * A) + B != MAP[i + 1]) {
						Flag = false; // 아니라면 false
						break;
					}
				}
				if (Flag) { // N개의 수가 정해진 규칙대로 나열됐다면 N+1번째 수를 구한다.
					cout << new_Number() << "\n";
				}
				else { // 규칙대로 나열되지 않았다면 잘못된 입력이다.
					cout << "B" << "\n";
				}
			}
			else { // A, B가 정수가 아니라면 잘못된 입력이다.
				cout << "B" << "\n";
			}
		}
	}

	return 0;
}