3752. 가능한 시험 점수

3752. 가능한 시험 점수

다른 분이 힌트를 주셔서 풀게 됐는데, 이런 방식의 문제를 어렴풋 본 것 같다.

처음에 DP라고 생각했지만, DP로 풀기에는 뭔가 이상하다 했는데, 쉬운 풀이 방법이 존재했다.

가능한 점수 범위가 10000까지기 때문에, 배열을 10000개 선언한다.

그리고 0 을 true 로 체크하고 시작한다, 

예를 들어 2, 3, 5점이라는 배점을 가지고 있을 때,

처음에 0 을 true 로 체크

그 다음에 배점은 2 이기 때문에

0 , 0+2 를 true 로 체크

다시 for문을 돌면서 배점이 3이기 때문에

0, 0+3, 0+2+3, 을 true 로 체크...

이런식으로 중복되는 값들을 간단하게 처리 할 수 있게 된다. 참으로 똑똑하고 쉬운 방법인거 같다.

<정답 코드>

#include<iostream>
#include<vector>
using namespace std;
 
int n, ans, sum;
int g[101];
bool used[101];
bool D[100001];
void init()
{
    ans = 0;
    sum = 0;
    for (int i = 0; i < 101; i++)
    {
        g[i] = 0;
        used[i] = false;
    }
 
    for (int i = 0; i < 100001; i++)
    {
        D[i] = false;
    }
}
 
 
int main()
{
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        init();
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> g[i];
            sum += g[i];
        }
        D[0] = true;
 
        for (int i = 0; i < n; i++)
        {
            for (int j = sum; j >=0; j--)
            {
                if (D[j])
                {
                    D[j + g[i]] = true;
                }
            }
        }
 
        for (int i = 0; i < 10001; i++)
        {
            if (D[i])
            {
                ans++;
            }
        }
        cout << "#" << t << " " << ans << "\n";
    }
    return 0;
}