[ SWEA / 3752 ] 가능한 시험 점수 (C++)

SW Expert Academy

 

난이도 : D4 
알고리즘 유형 : 완전탐색 
풀이 시간 : 53분 

문제 풀이 

N개의 문제 중 틀리면 0점, 맞으면 배점만큼 점수를 받는다. 학생들이 받을 수 있는 점수의 경우의 수는 총 몇 가지인지 구하는 문제이다.

 

문제를 간단하게 생각해보면, 받을까 ? 받지 않을까 ? 에 대해서만 생각하면 된다. 하지만, 문제의 총 개수가 $N ≤ 100$이기 때문에, 단순히 완전 탐색을 사용한다면, $O(2^{100})$으로 시간초과가 나게 된다.

 

따라서, 점수를 하나씩 더해가며, 받을 수 있는 점수 배열에 추가한 다음, 중복되는 단어는 visited 배열을 통해 가지치기를 진행해주는 방식으로 문제를 해결할 수 있다.

여기서, 중요하게 생각해야 할 부분은 받을 수 있는 점수 배열이 업데이트 되기 직전의 길이로 반복문을 순회해야 한다는 점이다.

for (int i = 0; i < n; i++) {
	int cur_size = scores.size();
	for (int j = 0; j < cur_size; j++) {
    }
}

배열의 사이즈를 사전에 정의하지 않고, scores.size()까지 j 변수를 순회하게 된다면, 추가적으로 생성된 새로운 점수 추가에 대한 영향을 받게 된다.

 

문제의 시간복잡도로는 최악의 경우, 2중 반복문을 100번만큼 돌기 때문에 $O(N^2)$이 소요된다.

 

코드

/*
틀리면 0점, 맞으면 배점만큼의 점수를 받는다.
학생들이 받을 수 있는 경우의 수는 몇 가지일까?

풀이 : 재귀로 모든 경우를 확인한다면 ? 2^100
그렇다면, 현재 생성된 값에다가 더해보자
-> 중복 숫자는 visited로 판단해서 넘기기
*/

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int t, n;
vector<int> scores;
int arr[101], visited[10001];

int main() {
	cin >> t;
	for (int tc=1;tc<t + 1;tc++) {
		cin >> n;
		
		for (int i = 0; i < n; i++)
			cin >> arr[i];
		scores.push_back(0);
		visited[0] = 1;

		for (int i = 0; i < n; i++) {
			int cur_size = scores.size();
			for (int j = 0; j < cur_size; j++) {
				int tmp = arr[i] + scores[j];
				if (!visited[tmp]) {
					visited[tmp] = 1;
					scores.push_back(tmp);
				}
			}
		}
		cout << '#' << tc << ' ' << scores.size() << '\n';
		memset(arr, 0, 101 * sizeof(int));
		memset(visited, 0, 10001 * sizeof(int));
		scores.clear();
	}
}

배운 점 

시간복잡도를 먼저 계산하고, 가능할 것 같은 알고리즘을 선택하려고 했는데, 이 문제의 경우 어떤 알고리즘을 사용했다고 하기에 살짝 애매한 것 같다.

2중 반복문을 통해 순회하는 문제는 맞지만, 업데이트가 되는 배열에 대한 계산 역시 가능하다는 것을 빠르게 인지해야 할 것 같다.