[백준 1111번] IQ Test

문제 링크

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

 

문제 요약

점화식 \(x_{i+1} = x_i * a + b\) 으로 만들어진 길이 \(N\)의 수열이 주어진다. \(a\), \(b\)를 찾아 수열의 다음 항을 출력하는 문제이다.

 

문제 번호도 그렇고 제목도 그렇고 뭔가 쉬워보이는 냄새가 난다. IQ Test 정도는 뭔가 쉽게 통과할 것 같은 근자감도 생긴다. 그렇게 9년 전의 나는 쉬운 마음으로 1111번에게 도전했다 참패했다. 9년이 지난 지금의 나는 어떨까?

 

9년전의 나보다 강해져서 다행이다

쉽진 않았지만 그래도 어찌저찌 9년 전 참패는 만회할 수 있었다. 구미가 당기는 번호, 쉬운 제목으로 사람을 현혹시키고 패배의 감정을 맛보게 해주는 악마의 문제 백준 1111번 풀이를 적어본다.

 

문제 풀이

세 개의 연속된 항 \(x_{i}\), \(x_{i+1}\), \(x_{i+2}\)을 가지고 다음 두 선형 점화식을 세울 수 있다.

1. \(x_{i+2} = x_{i+1} * a + b\)
2. \(x_{i+1} = x_{i} * a + b\)

이 두 식의 차를 이용해 다음과 같이 \(a\)를 계산할 수 있다.

 

\(a = \frac{x_{i+2} - x_{i+1}}{x_{i+1} - x_{i}}\)

 

여기서 \(a\)를 찾은 후, \(b\)의 값도 자연스럽게 구할 수 있다. 이 식만 놓고 본다면 정말 쉬워보이지만, 예외 케이스를 처리하는데서 이 문제의 진가가 나타난다.

 

예외 케이스 크게 두 가지가 있다.

1. 다음 항이 여러개일 수 있는 경우(A 출력)
2. 다음 항을 구할 수 없는 경우 (B 출력)

그리고 이 예외 케이스를 계산하기 위해서는 \(N\)에 따라 경우의 수를 나눠서 생각해야 한다.

N이 1인 경우

\(a\)와 \(b\)를 특정할 수 없으므로 A를 출력한다.

N이 2인 경우

• 첫 번째 수와 두 번째 수가 같다면, \(a\)는 1이고 \(b\)는 0이다.
• 두 수가 다를 경우, \(a\)와 \(b\)를 특정할 수 없으므로 A를 출력한다.

N이 3 이상인 경우

이제 위에서 구한 식을 활용하면 되는데 여기서도 다시 경우의 수가 나눠진다.

• 분자가 0이 되는 경우에는 \(a\)가 1, \(b\)는 0이다.
• 분자와 분모가 나눠떨어지지 않는 경우에 정수인 \(a\)와 \(b\)를 찾지 못한다는 의미이니 B를 출력한다.
• 함정들을 다 피하고 나서 세 개의 항을 임의로 선택해 \(a\)와 \(b\)를 계산한다.

그리고 정말 마지막으로 식을 통해서 얻은 \(a\)와 \(b\)로 만든 수열이 맞는지 확인하고 맞다면 다음 항을 계산해서 출력하고 아니라면 B를 출력한다.

 

소스 코드

#include <iostream>

int n, A[110];

using namespace std;

int main() {
    cin >> n;
    
    for (int i = 0 ; i < n ; ++i) {
        cin >> A[i];
    }
    
    if (n == 1) {
        cout << "A" << endl;
        
        return 0;
    }
    
    if (n == 2) {
        if (A[0] != A[1]) {
            cout << "A" << endl;
            
            return 0;
        } else {
            cout << A[0] << endl;
            
            return 0;
        }
    }
    
    int up = A[1] - A[2];
    int down = A[0] - A[1];
    
    if (down != 0 && up % down != 0) {
        cout << "B" << endl;
        
        return 0;
    }
    
    int a = down == 0 ? 1 : up / down;
    int b = A[1] - A[0] * a;
    
    for (int i = 0 ; i < n - 1 ; ++i) {
        if (A[i] * a + b != A[i + 1]) {
            cout << "B" << endl;
            
            return 0;
        }
    }

    cout << A[n - 1] * a + b << endl;
}