개요
이 튜토리얼에서는 가점과 감점 방식이 적용된 n개의 문제에서 나올 수 있는 서로 다른 점수의 개수를 구하는 프로그램을 작성해 보겠습니다.
예를 들어 총 10문항이 있고, 각 문항은 정답일 때 2점, 오답일 때 -1점(감점)이라고 가정해 봅시다. 우리의 목표는 학생이 시험에서 받을 수 있는 모든 점수 조합을 찾아내는 것입니다.
문제 해결 접근 방법
문제는 다음 단계에 따라 해결할 수 있습니다.
- 문항 수(n), 정답 가점(x), 오답 감점(y)을 초기화합니다.
- 가능한 점수를 저장할 집합(set)을 선언합니다. 집합은 중복된 값을 자동으로 제거해 주므로 서로 다른 점수만 남기기에 적합합니다.
- 0부터 문항 수까지 두 개의 중첩 반복문을 돌며 모든 경우를 탐색합니다.
- 첫 번째 반복 변수(i)는 맞힌 문항 수, 두 번째 반복 변수(j)는 답하지 않은 문항 수로 간주하고, 나머지 문항(n - i - j)은 모두 틀린 것으로 처리합니다.
- 계산된 총점을 집합에 삽입합니다.
- 집합의 크기를 출력하면 그 값이 곧 나올 수 있는 서로 다른 점수의 개수입니다.
예제 코드
위 알고리즘을 C++로 구현한 코드는 다음과 같습니다.
#include<bits/stdc++.h>
using namespace std;
int findPossibleMarksCount(int n, int x, int y) {
set<int> marks;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
// i = 정답 개수
// j = 미응답 개수
marks.insert((x * i) - ((n - i - j) * y));
}
}
return marks.size();
}
int main() {
int n = 20, x = 2, y = -1;
cout << findPossibleMarksCount(n, x, y) << endl;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
41
즉, 20문항에서 정답 시 2점, 오답 시 -1점인 조건에서 학생이 받을 수 있는 서로 다른 점수는 총 41가지입니다.
시간 복잡도
두 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n²)입니다. 집합(set)은 내부적으로 균형 이진 탐색 트리로 구현되어 삽입 연산에 로그 시간이 소요되지만, 실제로 저장되는 서로 다른 점수의 개수는 제한적이므로 전체 성능에 큰 영향을 주지 않습니다.
마무리
이처럼 집합 자료구조와 이중 반복문만 활용하면 복잡한 수학적 계산 없이도 가능한 모든 점수의 개수를 손쉽게 구할 수 있습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨 주세요.