ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 4012.요리사
    알고리즘/SW Expert Academy 2020. 8. 6. 22:41

    이번에 풀어볼 문제는 SW Expert의 4012번 요리사이다.

     

    SW Expert Academy

    SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

    swexpertacademy.com

    지금까지 풀었던 SW Expert 문제 중에 문제가 가장 애매하게 출제된 거 같다. 

    그 이유는 식재료에 대한 중복내용이 없기 때문에 어떻게 풀어아햐는건지 확실하지 않다고 느꼈기 때문이다.

    하여튼 간에 문제를 처음 읽어보면 어떤 부분이 애매한지 느낄 수 있을 것이다.

    애매한 부분만 빼면 재귀함수를 연습하기에는 괜찮은 문제인 거 같다 => 나는 재귀를 잘못해서 조금 골치아팠다..

     


     

    이 문제는 결론적으로 조합 문제이다. 결국 시너지를 만들어 내기 위함인데 두 가지의 조합이 들어가있다.

     

    1. 음식A와 B에 대한 조합

    => 식재료의 갯수의 / 2를 선택하는 조합을 우선 구현해야한다.

    => 예를 들어 6가지의 식재료가 있다고하면 6개중 6/2 => 3개 즉 6개중 3개를 고르는 조합을 구현해야한다.

     

    2. 그렇게 고른 3개의 식재료중 2개를 선택하는 조합

    => 3개중에 2개를 이용한 조합을 통해서 시너지의 크기를 구해야한다.

     

    나는 재귀함수를 이용해서 조합을 만들었다.

    개인적으로 식재료를 나눈거까지는 금방했는데 2번을 구현하는게 머리에 안떠올랐다..

    이런 부분이 부족한 거 같다.. 부족한 부분을 찾아서 다행이다.

    => 정답을 보면 이걸 왜 못떠올렸나 싶다..( 21 ~ 27번 라인 )

     


     

    < Code 설명 >

    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
    73
    74
    75
    76
    77
    78
    79

    #pragma
     warning(disable:4996)
    #include <iostream>
    #include <deque>
    #include <algorithm>
     
    #define MAX 17
     
    using namespace std;
     
    int T, N;
    int map[MAX][MAX]; // 식재료 map
    bool check[MAX];   // 식재료 사용여부
    int ans, syn;
    int sum1, sum2; // 음식A, 음식B의 시너지 변수
     
    deque<int>d1; // 음식 A의 식재료 그릇
    deque<int>d2; // 음식 B의 식재료 그릇
     
    void cook(){
        sum1 = sum2 = 0// 0으로 초기화
        for (int i = 0; i < syn; i++){
            for (int j = 0; j < syn; j++){
                if (i != j ){
                    sum1+=map[d1[i]][d1[j]]; // 음식 A의 시너지 구하기
                }
            }
        }
        for (int i = 0; i < syn; i++){
            for (int j = 0; j < syn; j++){
                if (i != j){
                    sum2 += map[d2[i]][d2[j]]; // 음식 B의 시너지 구하기
                }
            }
        }
        d1.clear(); // 음식A의 식재료 그릇 비우기
        d2.clear(); // 음식B의 식재료 그릇 비우기
        ans = min(ans, abs(sum1 - sum2)); // 시너지의 차이 중 최소 값을 저장
    }
     
    void search(int start, int cnt){ // 시작 index와 고른 식재료의 개수를 인자로 조합 진행
     
        if (cnt == syn){  // 총 식재료중 절반을 골랐다면
            for (int i = 0; i < N; i++){ 
                if (check[i])
                    d1.push_back(i); // 음식A에 선택한 식재료 저장
                else
                    d2.push_back(i); // 남은 식재료는 음식B에 사용되므로 따로 저장
            }
            cook(); // 음식만들기 시작! ( 고른 식재료들로 최대 시너지를 찾는 함수 )
            return;
        }
        
        for (int i = start; i < N; i++){ // 인자로 넘겨준 시작 idx를 사용하는것이 Point !!
            // 식재료 조합 재귀함수
            if (!check[i]){         // 고른적이 없다면
                check[i] = true;    // 고른다
                search(i, cnt + 1); // 고른 갯수 +1
                check[i] = false;   // 다음 탐색을 위해 고른것 취소
            }
        }
    }
     
    int main() {
        freopen("4012.txt""r", stdin);
        cin >> T;
        for (int z = 1; z <= T; z++){
            cin >> N;
            for (int i = 0; i < N; i++){
                for (int j = 0; j < N; j++){
                    cin >> map[i][j];
                }
            }
            ans = 987654321// 정답변수
            syn = N / 2;     // 식재료의 절반만 이용하여 시너지를 내야함
            search(0,0);     // 조합시작
            cout << "#" << z << " " << ans << endl;
        }
        return 0;
    }
    cs

    '알고리즘 > SW Expert Academy' 카테고리의 다른 글

    4012.요리사  (0) 2020.08.06
    2112.보호필름  (0) 2020.07.30
    1953.탈주범 검거  (1) 2020.07.28
    1952.수영장  (0) 2020.07.23
    2382.미생물격리  (0) 2020.07.21
    2383.점심 식사시간  (0) 2020.07.10

    댓글 0

Designed by Tistory.