반응형

문제 출처 :


https://www.acmicpc.net/problem/9882



알고리즘 분석 :


문제 해결에 필요한 사항

1. 재귀


이 문제는 재귀속 재귀를 4번 돌리면 되는 문제이다.


12명 중 3명을 고르고, 9명중 3명을 고르고, 6명중 3명을 고르고, 3명중 3명을 고르면


12C3 * 9C3 * 6C3 * 3C3이기에 4중 재귀여도 문제 해결이 가능하다.


우선 cnt == 3 즉, 3개를 고르면 ret라는 구조체 배열에 담아주고 구조체 배열이 4개가 되면 그때 최소,최댓값의 차를 구하며 계속 진행한다.


아래에 두가지 코드가 있는데 2번째 코드는 next_permutation을 조합으로 바꾸는 방법을 설명해두었다.


STL로 해결하면 훨씬 더 코드가 간결해진다.







소스 코드 : 


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
#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
struct INFO {
    int num[3];
};
 
INFO ret[4];
 
int arr[12];
bool visit[12];
 
int ans = 987654321;
void combination(int idx, int cnt, INFO info, int retCnt) {
    if (retCnt == 4) {
        int minVal = 987654231;
        int maxVal = -1;
 
        for (int i = 0; i < 4; i++) {
            int val = 0;
            for (int j = 0; j < 3; j++)
                val += ret[i].num[j];
 
            minVal = min(minVal, val);
            maxVal = max(maxVal, val);
        }
 
        ans = min(ans, maxVal - minVal);
 
        return;
    }
    if (cnt == 3){
        ret[retCnt] = info;
        info.num[0= info.num[1= info.num[2= 0;
        combination(00, info, retCnt + 1);
        return;
    }
 
    for (int i = idx; i < 12; i++) {
        if (!visit[i]) {
            visit[i] = true;
            info.num[cnt] = arr[i];
            combination(i + 1, cnt + 1, info, retCnt);
            info.num[cnt] = 0;
            visit[i] = false;
        }
    }
}
int main() {
    for (int i = 0; i < 12; i++)
        scanf("%d"&arr[i]);
 
    INFO info = { 0, };
    combination(00, info, 0);
 
    printf("%d", ans);
    
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
int perm[] = {000111222333};
int N, a[15], ans;
 
int main(){
    N = 12;
    for(int i = 0; i < N; i++)
        scanf("%d", a + i);
    ans = 1e9;
    do{
        int s[4= {0,};
        int mn = 1e9, mx = -1e9;
        for(int i = 0; i < N; i++)
            s[perm[i]] += a[i];
        for(int i = 0; i < 4; i++){
            mx = max(mx, s[i]);
            mn = min(mn, s[i]); 
        }
        ans = min(ans, mx - mn);
    }while(next_permutation(perm, perm + 12));
    printf("%d\n", ans);
    return 0;
}
cs

반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[16159번] 전광판의 숫자  (0) 2018.09.22
[15965번] K번째 소수  (0) 2018.09.21
[15927번] 회문은 회문아니야!!  (0) 2018.09.19
[5670번] 휴대폰 자판  (0) 2018.07.15
[2591번] 숫자 카드  (0) 2018.06.30