[SWEA][D4][c++] 3752. 가능한 시험 점수

문제

3752. 가능한 시험 점수

 

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWHPkqBqAEsDFAUn

SW Expert Academy

 

풀이 과정

 

ex) n의 값이 2,3,5가 주어졌을 때

 

 

1.문제에서 주어진 최대 결과값 10001길이의 socre 배열을 선언한다

2.주어진 수를 한개씩 입력 받고 sum변수에 더한다.

3.입력을 하나씩 받을때 마다 sum 변수 부터 0 까지 socre 배열을 탐색하면서 socre[index]값이 0보다 크면 index값에 현재 주어진 수의 값을 더한 위치 score[index+주어진 수]에 1을 더한다.

4. 2~3의 반복과정을 끝낸후 0부터 sum 변수까지 socre[] 배열의 값이 0보다 큰 값의 개수를 구하여 출력한다.

 

코드

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

int main(int argc, char** argv)
{
    int arr[100];
    int score[10001];
	int test_case;
	int T;
	cin>>T;
	for(test_case = 1; test_case <= T; ++test_case)
	{
        int n;
        int sum=0;
        int ans=0;
        cin >> n;
        memset(arr,0,sizeof(arr));
        memset(score,0,sizeof(score));
        
        score[0]=1; // 0은 항상 존재
        
        for(int i=0; i<n; i++){
            cin >> arr[i];
            sum+=arr[i];
            for(int j=sum; j>=0; j--)
                if(score[j]>0)
                    score[j+arr[i]]++;      
        }
             
        // 중복을 제외한 값 찾기
        for(int i=0; i<=sum; i++)
        	if(score[i]>0)
                ans++;
            
        cout <<"#"<<test_case<<" "<<ans<<"\n";
       
	}
	return 0;
}