C++로 출석률 75% 유지에 필요한 최소 강의 수 구하는 프로그램

이 문제에서는 지금까지 진행된 총 강의 수 M과 학생이 출석한 강의 수 N이 주어집니다. 목표는 출석률을 75% 이상으로 유지하기 위해 앞으로 추가로 출석해야 하는 최소 강의 수를 구하는 프로그램을 C++로 작성하는 것입니다.

문제 설명

대학생들에게 출석률 75% 유지는 가장 큰 고민 중 하나입니다. 많은 대학에서 출석률이 일정 기준에 미달하면 시험 응시 자격을 잃거나 과목 이수가 어려워질 수 있기 때문입니다. 이 프로그램은 현재까지의 출석 현황을 바탕으로, 학생이 정기적으로 출석해야 할 최소 강의 수를 계산해 줍니다.

예시를 통해 문제를 자세히 이해해 보겠습니다.

예제 1

입력: M = 32, N = 20

출력: 16

설명: 출석률 75%를 달성하려면 최소 16개의 강의를 더 출석해야 합니다. 그러면 총 강의 수는 48개, 출석한 강의 수는 36개가 됩니다.

출석률 = 36 × 100 / 48 = 75%

예제 2

입력: M = 14, N = 4

출력: 26

설명: 출석률 75%를 달성하려면 최소 26개의 강의를 더 출석해야 합니다. 그러면 총 강의 수는 40개, 출석한 강의 수는 30개가 됩니다.

출석률 = 30 × 100 / 40 = 75%

해결 방법

방법 1: 반복문을 이용한 접근 — O(n)

가장 직관적인 방법은 총 강의 수와 출석 강의 수에 각각 하나씩 강의를 추가해 가면서, 출석률이 75% 이상이 되는 순간 반복을 멈추고 그때까지 추가한 강의 수를 반환하는 것입니다.

솔루션의 동작을 보여주는 프로그램입니다.

#include <iostream>
using namespace std;

int maintainAtt(int M, int N) {
    int att = 0;
    while (1) {
        if (((N + att) * 100) / (M + att) >= 75) {
            return att;
        }
        att++;
    }
}

int main() {
    int M = 23, N = 12;
    cout << "출석해야 할 총 강의 수는 " << maintainAtt(M, N);
    return 0;
}

출력

출석해야 할 총 강의 수는 21

이 방법은 반복문을 사용하므로 시간 복잡도가 O(n)입니다. 하지만 수학적 공식을 활용하면 O(1)의 시간 복잡도로 해결할 수 있습니다.

방법 2: 수학 공식을 이용한 접근 — O(1)

추가로 출석해야 할 강의 수를 x라고 하면, 다음 부등식이 성립해야 합니다.

(N + x) / (M + x) ≥ 0.75

이 식을 x에 대해 정리하면 다음과 같습니다.

x ≥ (0.75 × M − N) / 0.25

따라서 출석률 75%를 유지하기 위해 필요한 최소 강의 수는 아래 공식으로 구할 수 있습니다.

최소 출석 강의 수 = ⌈(0.75 × M − N) / 0.25⌉

솔루션의 동작을 보여주는 프로그램입니다.

#include <iostream>
#include <math.h>
using namespace std;

int maintainAtt(int M, int N) {
    int att = ceil(((0.75 * M) - N) / (0.25));
    return att;
}

int main() {
    int M = 30, N = 11;
    cout << "출석해야 할 총 강의 수는 " << maintainAtt(M, N);
    return 0;
}

출력

출석해야 할 총 강의 수는 46

마무리

반복문을 사용하는 첫 번째 방법은 구현이 간단하지만, 필요한 강의 수가 커지면 실행 시간이 그만큼 길어진다는 단점이 있습니다. 반면 수학 공식을 활용하는 두 번째 방법은 입력 크기와 무관하게 상수 시간 안에 결과를 계산하므로 훨씬 효율적입니다. 실제 코딩 테스트나 실무 환경에서는 O(1) 공식 기반 접근 방식을 사용하는 것이 권장됩니다.