[백준/BOJ] 3474번 : 교수가 된 현우, 22864번 : 피로도, 13458번 : 시험 감독

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 3474번 : '교수가 된 현우', 22864번 : '피로도', 13458번 : '시험 감독' 문제의 풀이 코드와 해설을 다루고 있습니다.

 

문제 난이도는 Bronze ~ Silver 티어에 해당하며, 랜덤으로 문제를 골라 풀이하는 중이므로 카테고리 역시 랜덤입니다.

 

 

3474번 : 교수가 된 현우

 

N!이 10의 몇 제곱을 약수로 가지는지 구하는 문제입니다.

1 ~ N의 수에 대해 2와 5 약수의 개수를 모두 count 해주는 방법이 가장 쉽겠지만, 시간 초과가 발생하므로 더 빨리 구할 수 있는 방법을 찾아야합니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int T; cin >> T;

    while(T--) {
        int N; cin >> N;

        int two = 0, five = 0;

        int temp = 2;
        while(temp <= N) {
            two += N / temp;
            temp *= 2;
        }

        temp = 5;
        while(temp <= N) {
            five += N / temp;
            temp *= 5;
        }

        cout << min(two, five) << "\n";
    }
}

 

저는 위와 같이 구현하였는데, N에 대해 2로 나눈 몫, 2^2로 나눈 몫, 2^3으로 나눈 몫, ... 을 모두 합하는 식으로 계산하였습니다.

그렇게 된다면 2로 나눈 몫에서 2^1을 약수로 가진 수들의 개수가 나오므로 이들이 모두 카운트 되고, 그 다음 2^2로 나눈 몫에서는 2^2을 약수로 가진 수들의 개수가 나오므로 카운트 되고, ... 하는 방식이 반복되면서 모두 카운트할 수 있기 때문입니다.

 

이를 5에 대해서도 마찬가지로 해준 후 2와 5 중 더 수가 적은 것이 결국 10의 거듭제곱의 수를 결정하므로 그 값을 출력해주면 됩니다.

 

 

 

 

22864번 : 피로도

 

24시간인 하루에 1시간 단위로 일을 했을 때 피로도는 A만큼 쌓이고, 일은 B만큼 처리할 수 있으며 피로도가 M 이하로 유지되도록 할 때 최대 얼마나 많은 일을 처리할 수 있는지 묻는 문제입니다.

 

가장 간단한 형태의 그리디 문제이므로, 일을 할 수 있는 상황에서는 일을 최대한 처리하고 그 외의 경우에는 휴식을 취하도록 구현해주도록 하겠습니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int A, B, C, M; cin >> A >> B >> C >> M;

    int ans = 0, curr = 0;

    for(int time = 0; time < 24; time++) {
        if(curr + A <= M) {
            curr += A;
            ans += B;
        }
        else curr = max(curr - C, 0);
    }

    cout << ans;
}

 

구현은 위에서 설명한대로 그대로 코드를 작성하면 되며, 주의해야할 점은 피로가 0 미만으로 내려갈 수 없으므로 코드에서 현재 피로도를 의미하는 curr = max(curr - C, 0)으로 설정하여 0 미만으로 내려가지 못하게 작성해줍니다.

 

나머지는 간단하게 구현 가능하며, 위의 풀이 코드에서 ans는 답으로 출력할 "일의 양"을 의미합니다.

 

 

 

 

13458번 : 시험 감독

 

N개의 시험장 각각에 최소 총감독관 1명과, 부감독관은 자유로운 수로 배치가 가능하다고 하며 감독관의 종류에 따라 감시 가능한 사람의 수가 다르다고 할 때, 모든 응시생을 감독하기 위한 최소 감독관의 수를 구하는 문제입니다.

 

문제 조건을 잘 읽어보면 총감독관은 무조건 배치를 한 명 이상씩 해야하므로, 총감독관을 배치한 이후 각 시험장에 남은 학생수에 따라 부감독관을 적절히 배치해주면 되는 문제입니다.

 

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<int> num(N);
    for(int i=0; i<N; i++) cin >> num[i];

    int A, B; cin >> A >> B;

    long long ans = N;
    for(int i=0; i<N; i++)
        if(num[i] > A) ans += (num[i] - A - 1)/B + 1;

    cout << ans;
}

 

위와 같이 for문 아래에 if문을 두어 num[i] > A인 경우 즉, 총 감독관을 배치하고도 감시해야할 학생이 더 있는 경우에만 부감독관을 필요한만큼 배치하여 ans에다가 더해주면 됩니다.

 

그리고 이 문제에서 주의할 점은 고사장의 수는 100만 이하이며 각 고사장에 존재 가능한 학생 수도 100만 이하이므로 필요한 감독관의 수가 int 범위를 벗어날 수 있습니다.

따라서 long long으로 ans를 선언하여 사용해주는 편이 좋습니다.