[C++] IQ Test (백준 1111번)

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

 

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    set<int> ans;
    for (int a = -200; a < 201; a++) {
        for (int b = -20000; b < 20001; b++) {
            bool psb = true;
            for (int i = 1; i < n; i++) {
                if (a * arr[i - 1] + b != arr[i]) {
                    psb = false;
                    break;
                }
            }
            if (psb) {
                ans.insert(a * arr[n - 1] + b);
            }
        }
    }

    if (ans.size() == 1) cout << *ans.begin() << '\n';
    else if (ans.size() > 2) cout << "A\n";
    else cout << "B\n";
}

무지성으로 모든 a, b 조합을 체크해서 풀었다...

처음에는 a와 b 범위 모두 -100 ~ 100으로 잡았다가 WA를 받았다. 그 후 범위가 부족함을 깨닫고 범위를 늘려줬다. 무지성으로 너무 늘리면 또 시간초과를 받게 되니 딱 리미트에 맞춰서 설정해주어야 하는 것 같다. 나는 a 범위 -200 ~ 200, b 범위 -20000  ~ 20000으로 설정해서 AC를 받았다. 

(AC)

 

범위 설정할 때 참고한 글

https://www.acmicpc.net/board/view/114710

https://www.acmicpc.net/board/view/107405

 

연립방정식을 사용하면 더 복잡하긴 하지만 시간을 많이 줄일 수 있는 것 같다. 나중에 풀어봐야겠다.

 

참고하면 도움이 될 글 

https://www.acmicpc.net/board/view/128337