SWEA[4012] - 요리사

링크

SWEA[4012]

문제설명

• N개의 요리재료를 N/2개의 2개의 Subset으로 만든 후 계산.

문제풀이

• Subset을 Arraylist에 저장

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Solution4012 {

    public static int N;
    public static int[][] synergy;
    public static int Ans=Integer.MAX_VALUE;

    public static ArrayList<Integer> sub1 = new ArrayList<Integer>();
    public static ArrayList<Integer> sub2 = new ArrayList<Integer>();

    public static int A;
    public static int B;

    public static void Subset(int cnt, int start) {
        if(cnt==N/2) {
            sub2.clear();
            for (int i = 0; i < N; i++) {
                if(!sub1.contains(i)) {
                    sub2.add(i);
                }
            }
//            System.out.println(sub1);
//            System.out.println(sub2);
//            System.out.println();

            A=0;
            B=0;

            for (int i = 0; i < N/2; i++) {
                for (int j = 0; j < N/2; j++) {
                    A+=synergy[sub1.get(i)][sub1.get(j)];
                    B+=synergy[sub2.get(i)][sub2.get(j)];
                }
            }
            Ans = Math.min(Ans, Math.abs(A-B));

        }
        for (int i = start; i < N; i++) {
            if(!sub1.contains(i)) {
                sub1.add(i);
                Subset(cnt+1, i);
                sub1.remove(new Integer(i));
            }
        }
    }

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/swea/4012.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T=Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= 10; test_case++) {

            N = Integer.parseInt(br.readLine());
            synergy = new int[N][N];
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    synergy[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            Subset(0,0);


            System.out.println("#"+test_case+" "+Ans);
            /*
             * 초기화
             */
            Ans=Integer.MAX_VALUE;
            sub1.clear();
            sub2.clear();
        }//end test_case
    }//end main
}

아쉬운점

• Subset만들때 16C8의 경우의 수에서 %2 할 수 있는데 어떻게 할지 모르겠음.
• 문제 이해를 제대로 못했음
  • 메뉴를 2개씩밖에 선택 못하는게아니라 N/2개씩 아예 반반으로 나누는 것임.
  • 시너지는 synergy[i][j] + synergy[j][i] 하는것임
• 테케가 10개만 맞은 경우가 있었는데 그 경우는 Test_case for문에 test_case<=10 이었음...

잘한점

• O(N) = 16C8 = 12870
• Subset1만들면 Subset2자동으로 만들어지는데 Array로 하려니 번거로워서 Arraylist사용함
  • Arraylist 초기화 안까먹음
• 조합은 이제 빠르게 짠다. [30분]