[2일차][재귀함수] 작업지시하기

- 문제 설명

N개의 일을 N명의 사람이 맡아 할때 가장 빠른 처리 시간 구하기

	1	2	3
A	2	1	2
B	5	8	5
C	7	2	2

위 같은 경우엔 A가 2번일, B가 1번일, C가 3번일을 해서 총 1+5+2로 8이 최소

- 입력

1 // 테스트 케이스

3 // N값

2 1 2 // 작업배열

5 8 5

7 2 2

- 출력

#1 8 // 테스트케이스 최소 시간

- 입력 예시

3
3
2 1 2
5 8 5
7 2 2
3
9 4 7
8 6 5
5 3 7
5
5 2 1 1 9
3 3 8 3 1
9 2 8 8 6
1 5 7 8 3
5 5 4 6 8

- 출력 예시

#1 8
#2 14
#3 9

- 코드

#include "stdio.h"

int N;

int work[10][10]; // 작업량 배열

int permutation[10]; // 순열을 구하는 배열

int number[10]; // N개만큼 숫지가 들어있는 배열

int numberUsed[10]; // N개의 숫자 중 사용한 숫자를 표시하는 배열

void getMinWorkTime(int startCount, int numberOfWork,int totalWorkTime);

int minWorkTime; // 최소 합

int main(int argc, const char * argv[]) {

    int T;

    scanf("%d", &T);

    for(int tc = 1;tc <= T;tc++)

    {

        scanf("%d",&N);

        for(int i = 0; i< N; i++) // 일 초기화

        {

            for(int j = 0; j<N;j++)

            {

                scanf("%d",&work[i][j]);

            }

        }

        for(int i=1;i<=N;i++) // 숫자 배열 채우기

            number[i-1] = i;

        for(int i=0;i<N;i++) // permutation사용 숫자 표시하는 배열 초기화

            numberUsed[i] = 0;

        for(int i=0;i<N;i++) // minSum 초기값 넣기(임의로 대각선으로 일했을 때의 값을 넣음)

        {

            minWorkTime+=work[i][i];

        }

        getMinWorkTime(0,N,0);

        printf("#%d %d\n",tc,minWorkTime);

    }

    return 0;

}

void getMinWorkTime(int startCount, int numberOfWork,int totalWorkTime)

{

    if (startCount == numberOfWork) // 마지막일 경우

    {

        if(minWorkTime > totalWorkTime) // 총 근무시간이 최소 근무시간보다 작으면 최소 근무시간 치환

        {

            minWorkTime = totalWorkTime;

        }

        return ;

    }

    else if(totalWorkTime > minWorkTime) // 현재까지 합이 최소 근무 시간보다 크면 취소(더 더해봤자 시간만 감)

        return ;

    else

    {

        for(int i=1;i<=numberOfWork;i++)

        {

            if(numberUsed[i-1] == 0) // 아직 사용하지 않은 수라면

            {

                permutation[startCount] = number[i-1]; // 순열 배열에 현재 숫자를 넣고

                numberUsed[i-1] = 1; // 그 숫자를 사용했다고 표시

                getMinWorkTime(startCount+1,numberOfWork,totalWorkTime+work[permutation[startCount]-1][startCount]); // 카운트를 늘리고 총 일한 시간을 현재 선택한 숫자의 작업시간을 더해줌

                numberUsed[i-1] = 0; // 이 라인에 오는 경우는 getMinWorkTime 재귀함수가 return되는 경우, 선택한 숫자를 다시 사용해야하기 때문에 사용표시를 초기화 해준다.

            }

        }

    }

}