[SWEA] 3753. 가능한 시험 점수

#3753. 가능한 시험 점수

SW Expert Academy

#풀이

 

각각 배점이 있는 N개의 문제를 풀어 맞출 수 있는 모든 점수의 경우의 수를 구하는 문제이다.

 

나와 있는 예시를 보면

2점, 3점, 5점 으로 3문제가 있고 3문제를 통해 받을 수 있는 모든 경우의 점수는

0, 2, 3, 5, 7, 8, 10 으로 총 7개의 경우가 나온다.

 

이걸 보고 2+3와 5가 같으므로 중복을 제거하는 set을 사용하려고 했지만 시간초과가 났다. 중복을 찾는 것이 오래 걸린 것 같다.

 

그래서 다음으로 생각한 것이 dp를 이용하여 푸는 방법이다.

 

2점의 점수가 들어오는 경우

{0} -> {0, 2}

 

3점의 점수가 들어오는 경우

{0, 2}, {0, 2, 0+3, 2+3}

 

5점의 점수가 들어오는 경우

{0,2,3,5} -> {0, 2, 3, 5, 0+5(중복), 2+5, 3+ 5, 5+5} 

 

이러한 방식으로 구할 수 있다.

그래서 N은 100개이고 숫자는 100까지 입력할 수 있으므로 

나올 수 있는 모든 점수의 개수는 100*100(10000)개이다.

 

동일한 숫자의 개수는 중요하지 않고 그냥 있는지 확인만 필요하기 때문에 

bool vis[10000] 배열을 만들어 숫자가 나왔는지 확인할 수 있도록 했다.

 

vis 배열의 값이 true 인 개수만 계산하여 출력하면 쉽게 풀 수 있다.

 

주의해야 할 점은 나는 입력받자마자 계산을 하기 때문에 새로 추가해야하는 숫자들을 따로 저장해놨다가 vis 배열에 값을 변경해야 한다.

#코드

#include<iostream>
#include<vector>
using namespace std;

int main(int argc, char** argv)
{
	int test_case;
	int T;
    ios::sync_with_stdio(0);
    cin.tie(0);

	cin>>T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for(test_case = 1; test_case <= T; ++test_case)
	{
		int n;
       	bool vis1[10001];
        fill(vis1, vis1+10001, false);
        
        int ans = 0;
        cin >> n;
		for(int i= 0; i < n; i++){
        	int num;
            vector<int> vis2;
            cin >> num;
            if(i == 0)
                vis1[num] = 1;
            else{
                for(int j = 1; j <=10000; j++){
                	if(vis1[j] == 0) 
                        continue;
                    vis2.push_back(j+num);
                }
                vis1[num] = 1;
                for(int i  = 0; i < vis2.size(); i++){
                	vis1[vis2[i]] = 1;
                }
            }
        }
        for(int i = 1; i <=10000; i++){
                	if(vis1[i] == 1) 
                        ans++;
        }
		cout << '#' << test_case << ' ' << ans + 1 << '\n';
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}