[백준 BOJ] 3711번 학번 (C++/cpp)

문제 설명

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

3711번: 학번

 

접근 방법 - 브루트포스 알고리즘을 이용한 연산 문제

백준의 3711번 문제는 브루트포스 알고리즘을 응용하여 해결해야 하는 문제이다.

해당 문제는, 각 테스트 케이스에서 주어진 학번을 나누었을 때 서로 다른 나머지가 나오는 어떤 수의 최솟값을 출력해야 하는 문제이다.

필자의 경우엔 각 학번에 대해 어떤 수로 나누었을 때의 나머지를 저장하는 배열을 선언하여 문제를 해결하였다.

하지만 문제 특성상 브루트포스 알고리즘을 이용해야하기 때문에 노가다를 해야 하는 것은 사실상 어쩔 수가 없다 (...)

혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면, 아래의 설명과 코드를 참고해보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

 코드의 실행 순서

1) 테스트 케이스의 수(t)를 입력받는다.

 

2) t의 크기만큼 반복문을 실행하여 아래의 연산을 취한다.

- 학번의 개수(num)를 입력받고, num의 크기만큼 학번(arr)을 입력받는다.

- 학번들을 나누어볼 숫자(result)를 0으로 초기화하여 선언한다. 

- 무한 반복문을 설정하여 아래의 연산을 순차적으로 실행한다.

- result에 1을 더한다. 
- 나머지를 저장할 배열(extra)을 모든 배열값을 0으로 초기화하여 선언한다.
- 만약 나머지가 같은 경우가 나타날 때 연산을 다시 시도하기 위해 변수 retry를 0으로 초기화하여 선언한다.
- 학번들을 하나씩 탐색하며 result로 나누어 나머지를 확인한다.
이때 연산된 나머지를 배열 번호로 갖는 extra의 배열값에 1을 더하도록 한다.
여기서 해당 extra의 배열값이 1을 넘어간다면 retry에 1을 더한 뒤 탐색을 종료하도록 한다.
- 위 연산 반복문이 종료되었을 때, retry의 값이 0이 아니라면 continue를 통해 해당 무한 반복문의 처음으로 돌아가도록 한다.
- 만약 위 continue를 실행하지 않았다면 나머지들이 모두 다르다는 것을 의미한다.
따라서 이 경우엔 현재 result 값을 출력한 뒤, 다음 테스트 케이스를 실행하도록 한다.

 

3) 모든 테스트 케이스들이 실행되었다면, 실행 종료하도록 한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 3711번 코드
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);   cout.tie(NULL);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int num;
        cin >> num;
        int* arr = new int[num];
        for (int j = 0; j < num; j++) {
            cin >> arr[j];
        }

        int result = 0;     // 답 저장할 변수
        while (true) {
            result++;
            int retry = 0;     // 0일때는 출력, 1일때는 다시 나눗셈 수행
            int extra[100001] = { 0 };   // 나머지 저장 (10만까지 해야함)
                // 보통은 연결리스트로 하는 것 같음
            for (int j = 0; j < num; j++) {
                extra[arr[j] % result]++;
                if (extra[arr[j] % result] > 1) {   // 같은 나머지 2개 이상일 때
                    retry++;
                    break; 
                }
            }
            if (retry > 0) { continue; }
            cout << result << endl;   break;
        }
    }
}

 

제출 결과

(2022.09.17 백준 3711번 문제 제출 결과)

연결리스트 극혐 읍읍