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

목표: SWexpert Academy 4012 [모의 SW 역량테스트] 요리사 문제 풀기

환경: mac OS High Sierra 10.13.4, CLion

이 문제 또한 완전탐색으로 풀려고 합니다. 완전탐색이란 문제의 답을 찾는 것인데, 가능한 경우를 모두 나열하고, 각각이 해가 될 수 있는지 확인하는 방법입니다.

우선 완전탐색의 장단점을 얘기해보자면 장점으로는 어떻게든 답을 구해낼 수 있다는 것이에요. 모든 경우를 다 살펴보고 해를 구하는 것이니까요. 단점은 문제의 조건에 따라 오래 걸린다는 것인데, 이것을 최적화 하는 방법들이 있어요. 가지치기라든지 백트래킹이라든지

로직

두명의 손님에게 음식을 제공하려고 합니다. 그리고 N개의 식재료가 있습니다. 식재료는 N/2 개씩 나누어 두 개의 요리하려고 합니다. (N은 짝수)

가상의 요리사 A, B가 있습니다. food[]라는 배열을 통해 N개의 식재료들을 나열해놨습니다. A,B 요리사는 각각 N/2개씩 식재료를 찜해놓습니다.

    food[inx] = 1; // inx번째 식재료는 A요리사가 찜
    solve(inx+1, aCnt+1, bCnt); 
    food[inx] = 2; // inx번재 식재료는 B요리사가 찜
    solve(inx+1, aCnt, bCnt+1);

위 코드가 익숙하지 않으신분들은 알파벳 문제를 빠르게 보시는게 좋습니다. 재귀를 통해 조합문제를 푸는 것인데, 뛰어나신분들이 해놓은 코드가 있으니 검색해보시길.

그럼 다시 식재료 찜하는 것을 언제까지하냐? 언제 재귀가 멈춰야하는지? 종료조건 == 모든 식재료가 찜 됐음. 그때에 식재료 선택이 끝났으니 calc()함수에서 시너지 계산하면 됩니다.

    if( inx == N){
        int tmp = calc();
        if(ans > tmp){
            ans = tmp;
        }
        return;
    }

그러면 안되는 경우는? 각각의 요리사가 찜한 요리의 식재료 수가 N/2보다 크면 안됩니다.

    if( aCnt > N/2 || bCnt > N/2){
        return;
    }

재귀함수의 시간복잡도는 solve 함수 내에서 solve를 두번씩 인덱스가 0~N-1까지 반복되다보니 O(2^N)이 됩니다. N크기가 (4 ≤ N ≤ 16)이므로 최악의 경우 2의 16승이므로 굉장히 작은 연산횟수입니다.

1초에 약 1억번 연산한다고 했을때 비해도 충분히 적은 횟수이무로 좋은 알고리즘이라고 생각합니다.

[제약사항]

  1. 시간 제한 : 최대 50개 테스트 케이스를 모두 통과하는 데 C / C++ / Java 모두 3초

  2. 식재료의 수 N은 4이상 16이하의 짝수이다. (4 ≤ N ≤ 16)

  3. 시너지 Sij는 1이상 20,000이하의 정수이다. (1 ≤ Sij ≤ 20,000, i ≠ j)

  4. i와 j가 서로 같은 경우의 Sij값은 정의되지 않는다. 입력에서는 0으로 주어진다.

요리사

code