삼성 SW 역량테스트 3752. 가능한 시험 점수

 

출처 https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

 

 

union find도 인덱스 0,1이 유니온 되고 0,2 가 유니온 되면 0,1,2 가 유니온 되지 못하므로 해답이 아님.

하나의 인덱스에 해당하는 배열값에 대해 먼저 기록 되고 그 다음 인덱스에 해당하는 배열이 그 기록을 참조하여 

새로운 값을 만들어 기록하고 그 다음 인덱스 배열 값이 또 그 기록을 참조하여 기록하면 자신을 중복하지 않고

여러개의 같은 인덱스가 중복되지 않는다.

 

백준의 소수의 곱 문제와는 다른 case!

 

 

#include <iostream>

using namespace std;


int arr[101];
bool visit[101];
bool total[10001];

void init()
{

for (int i = 0; i <= 100; i++)
{
arr[i] = 0;
visit[i] = false;
}
for (int i = 0; i <= 10000; i++)
{
total[i] = false;
}
}




int main(int argc, char** argv)
{
int test_case;
int T;

int N;



cin >> T;

for (test_case = 1; test_case <= T; ++test_case)
{


cin >> N;
int sum = 0;

init();



for (int i = 0; i < N; i++)
{
int a;
cin >> a;
sum += a;
arr[i] = a;

}


total[0] = 1;

for(int i = 0; i<N; i++)
for (int j = sum; j >= 0; j--)
{
if (total[j])
{
total[j + arr[i]] = true;
}
}



int count = 0;


for (int i = 0; i < sum + 1; i++)
{
if (total[i])
{   

count++;
}
}



cout << "#" << test_case << " " << count << endl;


}
return 0;//정상종료시 반드시 0을 리턴해야합니다.
}