Codeforces Round #748 (Div. 3)-D1. All are Same

문제 설명

요한은 정수 $a_1,a_2,...,a_n$으로 이루어진 길이가 $n$ ($n$은 짝수이다.)인 배열을 가지고 있다. 요한은 양의 정수 $k$를 생각해냈다. 그 후 배열에 다음 연산을 수행했다. 인덱스 $i(1\le i\le n)$ 를 선택하고 숫자 $a_i$에 $k$를 뺀다.

이러한 연산을 한번도 수행하지 않거나 한번 이상 수행하고 나서 배열에 있는 모든 원소가 같은 수로 만들고 싶다. 배열에 있는 모든 원소가 같은 수로 만들기 위해서 필요한 최대 $k$값을 구하자. 만약 이 숫자가 무수히 존재하면 $-1$ 을 출력한다.

Input
첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t(1\le t\le 10)$ 이 주어진다.

각 테스트케이스의 첫번째 줄에는 숫자 $n$ ($n$은 짝수이다.) $(4\le n\le 40)$ 가 주어진다.

각 테스트케이스의 두번째 줄에는 $n$개 정수 $a_1,a_2,....,a_n(-{10}^6\le a_i\le {10}^6)$ 이 주어진다.

Output
각 테스트케이스마다 이 배열에 수행할 수 있는 최대 정수 $k(k\le 1)$를 출력한다. 이 숫자가 무수히 존재하면 $-1$을 출력한다.

Example
input
3
6
1 5 3 1 1 5
8
-1 0 1 -1 0 1 -1 0
4
100 -1000 -1000 -1000

output
2
1
1100

문제 접근

사용한 알고리즘: 정수론, 수학
걸린 시간 : 00:06
업솔빙의 효과가 톡톡히 드러난 문제이다. 그래서 그런지 이번 문제 셋이 쉽더라도 개인적으로 엄청나게 만족했던 대회였다. 이전 대회 Codeforces Round #751 (Div. 2)에서 C번 문제를 기억하는가? 그 문제가 이번 문제의 약간 어려운 버전인데, 그 문제를 업솔빙 하면서 이 문제를 푸는 방식을 깨달았다. 애초에 저번 대회때 업솔빙을 제대로 했다면 이 문제는 쉽게 풀 수 있다. 단지 나는 $-1$ 처리를 순간 까먹어서 시간을 많이 잡아먹었지만 그래도 풀었기 때문에 난 만족한다.

이번 문제를 풀고나서 이 문제를 풀면 정수론 실력이 더욱 상승할 것이다.
C. Array Elimination 바로가기
해설

어느 한 수를 정해서 그 수가 되기 위해서 뺄 수 있는 최대 $k$값을 구해야한다. 일단 최대 $k$값을 구하는 것이기 때문에 배열에 있는 가장 작은 값을 기준으로 하는 것이 맞는 것 같다. 일단 배열에서 가장 작은 값을 std::min_element를 이용해서 구하고 모든 배열 값인 $a_i$에 최솟값을 빼면 $k$값의 후보들이 등장한다. 여기서 최대 $k$값을 구하려면 이 후보들 중에서 최대공약수를 구하면 쉽게 구할 수 있다. 이때 이 후보들의 값이 모두 같으면 최대공약수가 $0$이 되고, 이럴 때는 이미 같은 값으로만 이루어져 있다는 뜻이기 때문에 $k$값이 어느수던지 상관이 없다. 따라서 $-1$을 출력한다.

정답 코드

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        int arr[n];
        for(int i = 0; i < n ;i++) cin >> arr[i];
        int mn = *min_element(arr, arr + n);
        int ans = 0;
        for(int i = 0; i < n; i++){
            ans = __gcd(ans, arr[i] - mn);
        }
        cout << (ans == 0 ? -1 : ans) << "\n";
    }
}