알고리즘

1486. 장훈이의 높은 선반 (D4)

1q2w3e4r! 2018. 11. 5. 16:06

https://www.swexpertacademy.com/main/code/problem/problemSubmitHistory.do?contestProbId=AV2b7Yf6ABcBBASw


고려사항 


가장 낮은 탑의 크기와 선반의 높이의 차이로 정답을 구해야한다! 


풀이 방법


무식하게 모든 경우의 수를 구했다. B명의 직원중 1명 뽑아서 해보고 2명 뽑아서 해보고 ...B-1 뽑아서 해보고 B명 뽑아서 모든 경우를 다 조사해보았더니 남들의 문제 풀이보다 훨씬 시간이 오래 걸리게되었다. 

PASS가 나오긴 했지만 좀 가지치는 방법을 강구해보아야겠다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int T, N, B;
vector <int> imp;
int cha= 9999;
void hight()
{
    
    vector <int> v;
    int size = imp.size();
    for (int i = 1; i <= size; i++)
    {
        int num = size-i;
        v.clear();
        for(int k = 0; k < num; k++)
        {
            v.push_back(0);
        }
        for (int k = 0; k < i; k++)
        {
            v.push_back(1);
        }
        do 
        {
            int sum = 0;
            
            for (int vn = 0; vn < v.size(); vn++)
            {
                if (v[vn] == 1)
                {
                    sum += imp[vn];
                }
            }
            if (sum >= B)
            {
                int result = sum - B;
                cha = min(result, cha);
            }
 
        } 
        while (next_permutation(v.begin(), v.end()));
    }
}
int main()
{
    freopen("input.txt", "r", stdin);
    vector<int> ans;
    scanf("%d", &T);
    for (int testcase = 0; testcase < T; testcase++)
    {
        imp.clear();
        cha = 9999;
        scanf("%d%d", &N, &B);
        for (int i = 0; i < N; i++)
        {
            int H;
            scanf("%d", &H);
            imp.push_back(H);
        }
        hight();
        ans.push_back(cha);
    }
    for (int i = 0; i < ans.size(); i++)
    {
        printf("#%d %d\n" ,i + 1, ans[i]);
    }
 
}
cs