[SWEA] 4012번 : 요리사

나도 실력이 오른것인가. 원래 혼자 못풀었는데, 이제 혼자 풀었다! 히히

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH

SW Expert Academy

 

이 문제는 백준의 링크와 스타트와 아주 유사하당! 

사실 입출력 형식만 다르지 똑같다고 봐도 된당

 

[어떻게 풀었냐?]

1. solve : 우선 절반으로 쪼개서 A, B list에 각각 저장해둔다.

2. cal : 그리고 list에서 2개씩 뽑아서 각각의 음식의 맛을 계산해주면 된당. 

public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        for(int tc=1;tc<=T;tc++) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());

            map = new int[n+1][n+1];
            v = new int[n+1];
            res = new int[n+1];
            for(int i=1;i<=n;i++) {
                st = new StringTokenizer(br.readLine());
                for(int j=1;j<=n;j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            for(int i=1;i<=n;i++) {
                res[i]=i;
            }

            ans=Integer.MAX_VALUE; // 맛의 차이가 최소
            solve(1);
            System.out.println("#" + tc + " " + ans);
        }


    }

 

우선 입출력을 한바가지 받아주고

 

1. solve

부분집합을 활용해서 두 list의 개수가 같고, 두 list의 합이 n 과 같으면 정확히 절반으로 나눠진것이니까, 나눠진 list를 계산해주는 함수로 넘긴다.

static void solve(int depth){
        // 식재료 절반은 A
        // 나머지 절반은 B
        if(depth==n+1) {
            List<Integer> listA = new ArrayList<>();
            List<Integer> listB = new ArrayList<>();
            for(int i=1;i<=n;i++) {
                if(v[i]==1) { // A
                    listA.add(res[i]);
                }else { // B
                    listB.add(res[i]);
                }
                if(listA.size()==listB.size() && listA.size()+listB.size()==n) { // 절반
                    ans = Math.min(ans, cal(listA, listB));
                }
            }
            return;
        }

        v[depth]=1;
        solve(depth+1);
        v[depth]=0;
        solve(depth+1);
    }

 

2. cal

받은 배열 중에서 2개를 뽑아 i, j 의 index 로 두고, 각각 음식의 맛을 더해준 뒤, 두 음식의 맛의 차이를 return 해준다.

static int cal(List<Integer> A, List<Integer> B) {

        // A 음식의 맛
        int cntA=0;
        for(int i=0;i<A.size();i++) {
            for(int j=i+1;j<A.size();j++) {
                int x = A.get(i);
                int y = A.get(j);
                cntA+=(map[x][y] + map[y][x]);
            }
        }

        // B 음식의 맛
        int cntB=0;
        for(int i=0;i<B.size();i++) {
            for (int j = i + 1; j < B.size(); j++) {
                int x = B.get(i);
                int y = B.get(j);
                cntB += (map[x][y] + map[y][x]);
            }
        }

        return Math.abs(cntA-cntB);

    }

 

그럼 끝~! 

 

[전체코드]

import java.io.*;
import java.util.*;

class Main {

    static int n, map[][], ans=Integer.MAX_VALUE, v[], res[];

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        for(int tc=1;tc<=T;tc++) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());

            map = new int[n+1][n+1];
            v = new int[n+1];
            res = new int[n+1];
            for(int i=1;i<=n;i++) {
                st = new StringTokenizer(br.readLine());
                for(int j=1;j<=n;j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            for(int i=1;i<=n;i++) {
                res[i]=i;
            }

            ans=Integer.MAX_VALUE; // 맛의 차이가 최소
            solve(1);
            System.out.println("#" + tc + " " + ans);
        }


    }

    static void solve(int depth){
        // 식재료 절반은 A
        // 나머지 절반은 B
        if(depth==n+1) {
            List<Integer> listA = new ArrayList<>();
            List<Integer> listB = new ArrayList<>();
            for(int i=1;i<=n;i++) {
                if(v[i]==1) { // A
                    listA.add(res[i]);
                }else { // B
                    listB.add(res[i]);
                }
                if(listA.size()==listB.size() && listA.size()+listB.size()==n) { // 절반
                    ans = Math.min(ans, cal(listA, listB));
                }
            }
            return;
        }

        v[depth]=1;
        solve(depth+1);
        v[depth]=0;
        solve(depth+1);
    }

    static int cal(List<Integer> A, List<Integer> B) {

        // A 음식의 맛
        int cntA=0;
        for(int i=0;i<A.size();i++) {
            for(int j=i+1;j<A.size();j++) {
                int x = A.get(i);
                int y = A.get(j);
                cntA+=(map[x][y] + map[y][x]);
            }
        }

        // B 음식의 맛
        int cntB=0;
        for(int i=0;i<B.size();i++) {
            for (int j = i + 1; j < B.size(); j++) {
                int x = B.get(i);
                int y = B.get(j);
                cntB += (map[x][y] + map[y][x]);
            }
        }

        return Math.abs(cntA-cntB);

    }


}