SWEA 4012 [모의 SW 역량테스트] 요리사 C++

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

SW Expert Academy

 

최종 코드

• GitHub -> https://github.com/hwayeon351/SWEA-Algorithms/blob/main/SWEA4012.cpp

GitHub - hwayeon351/SWEA-Algorithms: SWEA 알고리즘 소스 코드 모음

//
//  main.cpp
//  SWEA4012
//
//  Created by Hwayeon on 2021/10/15.
//

#include <iostream>
#include <string.h>
using namespace std;

int N;
int synergy[17][17] = {0, };
int visit[17] = {0, };
int answer = 20001;

void make_food(int cnt, int i){
    if(cnt == N/2){
        int A = 0;
        int B = 0;
        for(int j=1; j<=N; j++){
            for(int k=1; k<=N; k++){
                if(j == k) continue;
                if(visit[j] && visit[k]){
                    A += synergy[j][k];
                }
                else if(!visit[j] && !visit[k]){
                    B += synergy[j][k];
                }
            }
        }
        int result = abs(A-B);
        if(result < answer) answer = result;
        return;
    }
    if(i > N) return;
    for(int j=i; j<=N; j++){
        visit[j] = 1;
        make_food(cnt+1, j+1);
        visit[j] = 0;
    }
}

int main(int argc, const char * argv[]) {
    int test_case;
    int T;
    cin >> T;
    for(test_case = 1; test_case<=T; ++test_case){
        answer = 20001;
        cin >> N;
        for(int y=1; y<=N; y++){
            for(int x=1; x<=N; x++){
                cin >> synergy[y][x];
            }
        }
        make_food(0, 1);
        cout << "#" << test_case << " " << answer << endl;
    }
    return 0;
}

---

풀이 과정

풀이 시간 23분

#include <iostream>
#include <string.h>
using namespace std;

int N;
int synergy[17][17] = {0, };
int visit[17] = {0, };
int answer = 20001;

void make_food(int cnt, int i){
	//재료 N/2개 뽑은 경우,
    if(cnt == N/2){
	//A = 음식 A의 맛, B = 음식 B의 맛
        int A = 0;
        int B = 0;
        for(int j=1; j<=N; j++){
            for(int k=1; k<=N; k++){
            	//재료가 같은 경우의 조합은 없다
                if(j == k) continue;
                
                //A의 두 재료 j, k 시너지 더하기
                if(visit[j] && visit[k]){
                    A += synergy[j][k];
                }
                
                //B의 두 재료 j, k 시너지 더하기
                else if(!visit[j] && !visit[k]){
                    B += synergy[j][k];
                }
            }
        }
        //음식 A와 B의 맛 차이
        int result = abs(A-B);
        if(result < answer) answer = result;
        return;
    }
    if(i > N) return;
    
    //재료 뽑기 -> 조합
    for(int j=i; j<=N; j++){
        visit[j] = 1;
        make_food(cnt+1, j+1);
        visit[j] = 0;
    }
}

int main(int argc, const char * argv[]) {
    int test_case;
    int T;
    cin >> T;
    for(test_case = 1; test_case<=T; ++test_case){
    	//answer 시너지의 최댓값은 20,000이므로 20,001로 초기화한다
        answer = 20001;
        cin >> N;
        for(int y=1; y<=N; y++){
            for(int x=1; x<=N; x++){
                cin >> synergy[y][x];
            }
        }
        make_food(0, 1);
        cout << "#" << test_case << " " << answer << endl;
    }
    return 0;
}
//시간복잡도 = T(T*2^N)-> O(N^2), 공간복잡도 = O(N^2)