ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [SWEA] 4012 요리사
    문제 풀이 2020. 5. 13. 23:03

    4012 요리사


    풀이)

    문제 자체는 어렵지 않았다.

    dfs를 이용해 각 음식마다 어떤 식쟤료를 가질건지 결정한 다음, 시너지 계산하는 완전 탐색 문제였다.


    그런데 처음에 시간초과 나길래 당황했다.

    알고보니, n개의 식재료가 있다면 음식 1을 위해 n/2 개까지만 고르고 나머지 쟤료들은 음식 2를 위해 쓰면되는데

    쓸데없이 식재료 n개의 나올 수 있는 모든 조합을 다 보고 있었다.

    즉, 음식 1을 위해 n/2개만 고르면 되는데 1~n개까지 고르는 경우를 다 확인한 것이다.

    (그리고 나서 n/2개씩일때만 계산하게 함)


    다시 풀때는 n/2개만 고르고 나머지들은 자동적으로 다른 음식 2를 위해 쓰이게 풀어줬다.


    코드)

    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
    #include <stdio.h>
    #include <vector>
    #include<algorithm>
    #include<cmath>
    using namespace std;
     
    #define INF 999999999;
     
    int n;
    int arr[16][16];
    int result;
    bool visited[16];
     
    void dfs(int idx,int depth) {
        if (depth == n/2) {
            vector <int> food[2];
            for (int i = 0; i < n; i++) {
                if (visited[i]) {
                    food[0].push_back(i);
                }
                else {
                    food[1].push_back(i);
                }
            }
            int cnt[2= { 0 ,0 };
            for (int i = 0; i < n / 2; i++) {
                for (int j = 0; j < n / 2; j++) {
                    if (i == j)continue;
                    cnt[0+= arr[food[0][i]][food[0][j]];
                    cnt[1+= arr[food[1][i]][food[1][j]];
                }
            }
            result = min(result, abs(cnt[0- cnt[1]));
            return;
        }
        for (int i = idx; i < n; i++) {
            visited[i] = true;
            dfs(i + 1, depth + 1);
            visited[i] = false;
        }
    }
     
    int main() {
        //freopen("sample_input (1).txt", "r", stdin);
        int T = 0;
        scanf("%d"&T);
        for (int test_case = 1; test_case <= T; test_case++) {
            scanf("%d"&n);
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    scanf("%d"&arr[i][j]);
                }
            }
            result = INF;
            
            dfs(00);
            printf("#%d %d\n", test_case, result);
        }
        return 0;
    }
    cs


    '문제 풀이' 카테고리의 다른 글

    [프로그래머스] 여행경로  (0) 2020.05.15
    [SWEA] 5656 벽돌깨기  (0) 2020.05.14
    [SWEA] 5650 핀볼게임  (0) 2020.05.12
    [SWEZ] 2383 점심 식사시간  (0) 2020.05.11
    [SWEA] 2117. 홈 방범 서비스  (0) 2020.05.09

    댓글

Designed by Tistory.