[SWEA] 4012 요리사 - JAVA

1. 문제

SW Expert Academy

식재료 i를 식재료 j와 같이 요리하게 되면 발생하는 시너지 Sij의 정보가 주어지고, 

가지고 있는 식재료를 이용해 A음식과 B음식을 만들 때, 

두 음식 간의 맛의 차이가 최소가 되는 경우를 찾고 그 최솟값을 정답으로 출력하는 프로그램을 작성하라.

---

2. 풀이

메인

static int min, N, halfN;
static int[][] items;

public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    StringBuilder sb = new StringBuilder();

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

    for (int tc = 1; tc <= T; tc++) {
        sb.append("#").append(tc).append(" ");
        N = Integer.parseInt(in.readLine());
        halfN = N / 2;
        items = new int[N][N];

        //시너지
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(in.readLine());
            for (int j = 0; j < N; j++) {
                items[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        min = Integer.MAX_VALUE;
        //조합이 중복되므로 첫번째 값 고정
        //findMin(0, 0,0);
        findMin(1,1,1);
        findMin(0, 0,0);

        sb.append(min).append("\n");

    }
    System.out.print(sb);
}

 

조합메서드

1.  start부터 N까지 돌고, 다시 부를 때 cnt와 start에 +1씩 추가한다. flag는 i번째에 1표시를 하기 위함이다.

2.  cnt==N의 절반이 되면 재귀를 멈춘다.

3.  0부터 N까지 돌면서 i와 j가 둘 다 1인지, 둘 다 0인지 확인한다. 둘 다 1인 걸 A로 삼아 a에 시너지를 더해주고, 반대의 경우를 B로 삼아 b에 시너지값을 더해준다. 

4.  마지막으로 static 변수 min과 |a-b|를 비교해 더 작은 값을 저장한다.

private static void findMin(int cnt, int start, int flag) {
    if (cnt == halfN) {
        int a = 0, b = 0;

        for (int i = 0; i < N - 1; i++) {
            boolean isA = (flag & 1 << i) != 0;

            for (int j = i + 1; j < N; j++) {
                if (isA && (flag & 1 << j) != 0) a += (items[i][j] + items[j][i]); //둘다 a가 뽑음
                else if (!isA && (flag & 1 << j) == 0) b += (items[i][j] + items[j][i]); //둘다 b가 뽑음
            }

        }

        min = Math.min(Math.abs(a - b), min);
        return;
    }

    for (int i = start; i < N; i++) {
        findMin(cnt + 1, i+1,flag | 1 << i);
    }
}

---

3. 결과

위의 코드가 훨씬 더 빠른데, 코드 한 줄만 변경한 결과다. (findMn(0,0,0) -> findMin(1,1,1)로 변경)

 

N/2를 뽑는 문제이기때문에 구한 조합 중 절반은 중복된다. 따라서 조합메서드를 부를때 카운트 1, start 1, flag 1을 설정해서 중복을 막는다.