BOJ_3711_학번 (C++)

[Silver V] 학번 - 3711

문제 링크

성능 요약

메모리: 2020 KB, 시간: 196 ms

분류

브루트포스 알고리즘, 수학, 정수론

제출 일자

2024년 12월 23일 22:34:45

문제 설명

Z 대학교 학생은 입학할 때 학번을 받게 된다. 학번은 0보다 크거나 같고, 10⁶-1보다 작거나 같은 정수이다. Z 대학의 김상근 교수는 학번으로 학생들을 구분한다. 상근이는 학생들을 조금 더 쉽게 기억하기 위해서 자신이 가르치는 학생들의 학번을 m으로 나누었을 때, 나머지가 모두 다른 가장 작은 양의 정수를 찾으려고 한다.

입력

첫째 줄에 테스트 케이스의 개수 N이 주어진다. 각 테스트 케이스의 첫째 줄에는 상근이가 가르치는 학생의 수 G가 (1 ≤ G ≤ 300) 주어진다. 다음 G개 줄에는 학생의 학번이 한 줄에 하나씩 주어진다. 학번이 같은 경우는 없다.

출력

각 테스트 케이스마다, 학번을 m으로 나눈 나머지가 모두 다른 가장 작은 정수 m을 출력한다.

문제 풀이

간단하게 m을 1부터 나누어보며 나머지를 저장시키고 모든 학생수만큼 진행했을 떄 겹치는게 없으면 그때가 최소 m이므로 출력.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

void solve() {
    int G;
    cin >> G;
    vector<int> students(G);

    for (int i = 0; i < G; i++) {
        cin >> students[i];
    }

    for (int m = 1;; m++) {
        vector<int> remainers;
        bool flag = true;

        for (int s : students) {
            int remainer = s % m;
            if (find(ALL(remainers), remainer) != remainers.end()) {
                flag = false;
                break;
            }
            remainers.push_back(remainer);
        }
        if (flag) {
            cout << m << "\n";
            break;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    cin >> tt;   // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}