#3752. 가능한 시험 점수

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWHPkqBqAEsDFAUn&categoryId=AWHPkqBqAEsDFAUn&categoryType=CODE

SW Expert Academy

 

n개의 수가 주어지고 n개만큼 점수를 입력한다.

예를들어 n=3이면

2 3 5를 입력하고 이때 나올 수 있는 모든 점수의 경우의 수를 출력하는 문제이다.

 

이때 가능한 모든 점수는

0 2 3 5 7 8 10 총 7가지이다.

 

이문제를 푸는 방법은 다음과 같다.

 

맨 처음 만들 수 있는 점수는 아무것도 선택하지 않는 0점은 모든 경우에서 동일하다.

 

그 후 2점을 선택하면 만들 수 있는 모든 경우는 0,1,2까지 인데 1점은 만들 수 있는 점수에 포함되지 않으므로 생략한다. 한편 만들 수 있는 점수에 0점이 있으므로 0점을 활용할 수 있다.

따라서 0점과 2점을 만들 수 있고 독립적으로 2점은 항상 true로 score배열에 추가시켜주어야 한다.

다음으로 3점을 보자. 이제 맥시멈 5점까지 만들 수 있다. 그 중 이미 만들어져 있는 수는 0,2이 이므로 3점을 합한 점수인 3,5점 까지 만들 수 있다. 이떄도 마찬가지로 합한 수에 3점이 추가가 안 되어 있을 수도 있으므로 독립적으로 3점을 score배열에 추가 시켜야 한다. 이와 같은 과정을 반복하게 되면 가능한 모든 경우의 수를 구할 수 있게 된다.

 

소스코드

 

 

	// #s 3752 가능한 시험 점수
	#include <iostream>
	#include <cstring>
	using namespace std;
	int visit[101];
	int score[10001];
	int arr[101];
	int result = 0;
	int n;
	int main() {
	int test;
	cin >> test;
	for (int t = 1; t <= test; t++) {
	memset(visit, 0, sizeof(visit));
	memset(score, 0, sizeof(score));
	result = 0;
	cin >> n;
	score[0] = true;
	int max = 0;
	for (int i = 0; i < n; i++) {
	cin >> arr[i];
	max += arr[i];
	for (int j = max; j >= 0; j--) {
	if (score[j]) {
	score[j + arr[i]] = true;
	}
	}
	score[arr[i]] = true;
	}
	for (int i = 0; i <= max; i++) {
	if (score[i])result++;
	}
	cout <<"#"<<t<<" "<< result << endl;
	}
	}

view raw [SWEA]3752.cpp hosted with ❤ by GitHub