[SWEA] 3752번 가능한 시험 점수

3752 가능한 시험 점수

풀이)

백준 2293 동전 문제와 비슷한 문제이다.

bool visited[10001]변수를 두어, 

점수들의 합 i이 나올 수 있을 경우 visited[i] = true로 바꿔줬다.

(크기를 10001로 둔 이유? 배점의 최고값 100 * n의 최대값 100 = 10000이므로)

코드)

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n;
int arr[100];
bool visited[10001];
 
int main() {
    //freopen("sample_input.txt", "r", stdin);
    int T = 0;
    scanf("%d", &T);
    for (int test_case = 1; test_case <= T; test_case++) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &arr[i]);
        }
        int Max = 0;
        visited[0] = true; //아무문제도 안맞췄을 경우 0점.
        for (int i = 0; i < n; i++) {
            Max += arr[i]; //새로운 점수 더해주고
            for (int j = Max; j >= 0; j--) { //이전에 가능한 점수 + 새로 받은 점수 체크해주기
                if (visited[j]) visited[j + arr[i]] = true;
            }
            visited[arr[i]] = true;
        }
        int result = 0;
        for (int i = 0; i < 10001; i++) {
            if (visited[i]) result += 1;
        }
        printf("#%d %d\n", test_case, result);
        
        fill(visited, visited + 10001, false);
        
    }
    return 0;
}