[4012] 요리사 in Java

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

SW Expert Academy

---

접근 방식

-> 조합을 써서 A팀의 재료를 뽑아준다.

이때 배열의 타입은 boolean, 크기는 N

그리고 해당 배열 중에 값이 false라면 A팀의 재료로 선택되지 않았기에

B팀의 재료에 해당한다. 

 

그래서 각팀의 음식맛을 구할 때

이중 for문을 돌려서

check의 값이 true라면 A팀의 재료이므로

teamA라는 변수에 더해주고

 

반대로 check의 값이 false라면 B팀의 재료이므로

teamB라는 변수에 더해준다.

 

 

 

 

---

시행 착오

- 2중 for문을 사용해서 하는 건 비효율적이라고 생각해서

좀 더 효율적으로 풀 수 있는 방식에 대해 생각해봤다.

하지만, 떠오르지 않았다..

좀 더 생각해봐야할 문제

 

 

 

 

package d0812;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution_4012_7조 {
    static int[][] array;
    static int N;
    static boolean[] check; // A팀 식재료
    static int answer;
    static int teamA;
    static int teamB;
    
    public static void comb(int cnt, int start) {
        if(cnt==N/2) {
            teamA=0; teamB=0;
            for (int i = 0; i < N; i++) {
                if(check[i]) { // A팀 
                    for (int j = 0; j < N; j++) {
                        if(check[j]) {
                            teamA+=array[i][j]; // A팀 음식 맛
                        }
                    }
                }else { // B팀 
                    for (int j = 0; j < N; j++) {
                        if(!check[j]) {
                            teamB+=array[i][j]; // B팀 음식 맛
                        }
                    }
                }
            }
            // A 음식과 B 음식의 맛의 차이가 최소가 되는 값 찾기
            answer=Math.min(answer, Math.abs(teamA-teamB));
            return;
        }
        for (int i = start; i < N; i++) {
            check[i]=true;
            comb(cnt+1, i+1); // A팀 식재료 선택
            check[i]=false;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T= Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            N= Integer.parseInt(br.readLine());
            array=new int[N][N];
            answer=Integer.MAX_VALUE;
            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    array[i][j]=Integer.parseInt(st.nextToken());
                }
            }
            check=new boolean[N];
            comb(0,0);
            System.out.println("#"+ t +" " + answer);
        }
    }
 
}