[C] 최단 시간에 다리 건너기 문제

www.notion.so/3-8a779ae91adc4df794668aacba06f1be

✔︎ 미션 3.최단 시간에 다리건너기

✔︎ 미션 3.

1. 미션 제목

최단 시간에 다리건너기

 

2. 지시문

N명의 사람들로 구성된 한 그룹이 밤중에 다리를 건너려고 합니다. 한 번에 최대 두 명 까지만 다리를 건널 수 있으며 다리 위를 지나가는 사람들은 반드시 손전등을 가지고 가야 합니다. n명의 사람들한테는 손전등이 한 개밖에 없기 때문에 남아 있는 사람들이 다리를 건너려면 어떤 식으로든 손전등을 가지고 다시 다리를 건너지 않은 사람들이 있는 곳으로 돌아가는 일을 해야합니다. 사람마다 다리를 건너는 속도가 다른데, 그룹의 속도는 가장 느린 구성원의 속도에 따라 결정됩니다. 가장 짧은 시간 안에 n명이 모두 다리를 건널 수 있는 방법과 그 시간을 출력하는 프로그램을 작성해봅시다.

입력으로 첫 줄에는 n이 입력되며 그 다음 줄부터 n개의 줄에 걸쳐서 각 사람들이 다리를 건너는 시간이 입력됩니다. 입력은 100명을 넘기지 않습니다.

출력은 맨 첫 줄에는 n명의 사람들이 모두 다리를 건너는데 걸리는 총 시간을 출력하고, 그 다음줄부터는 그 과정을 출력하면 됩니다. 이 때 각 줄에는 정수가 하나 또는 두 개가 들어가는데, 이 정수는 어떤 사람들이 다리를 건너가는지를 나타냅니다. 각 사람은 그 사람이 건너가는데 걸리는 시간으로 표시하며, 건너가고 오는 순서대로 출력해야 합니다. 최소 시간을 달성하는 방법이 여러가지가 있을 경우 그 중 아무 방법이나 출력해도 괜찮습니다. 완전한 프로그램을 작성하기 어려운 경우에는 pseudo code를 작성해도 좋습니다. 다만 이 경우에는 최대한 자세히 적어야 합니다. 숫자를 입력받는 부분은 따로 구현하지 않고 프로그램 내부에서 따로 선언하는 것으로 가정합니다.

 

예)

입력값:

4

1

2

5

10

 

출력값:

17

1 2

1

5 10

2

1 2

 

3. 핵심 개념

#정렬알고리즘

• 본 문제의 경우 문제를 푸는데 도움이 되는 힌트가 있습니다. 알고리즘의 경우 방법을 직접 고민해보고 찾는 것이 중요합니다. 때문에 고민을 하시다가 도저히 풀 수가 없을때 아래의 힌트를 참고해주시길 바랍니다.
• '각 사람들이 다리를 건너는 시간에 따라서 예)에 있는 출력값과 같은 방법으로 다리를 건너는 것이 최선이 아닌 경우도 있습니다. 어떤 경우에 그렇게 되는지, 그리고 그 때는 어떤 방법으로 다리를 건너는 것이 최선인지 생각해봅시다'

나의 풀이

아이디어

다리를 건너갈 때는 두 사람이 건너고 한 명이 손전등을 들고 다시 건너와야 한다. (2명 가고, 1명 돌아옴)

건너야 하는 사람들 중 느린 축에 속하는 사람들은 한번만 건너야 하고 손전등을 다시 전해주기 위해 갔다가 돌아오는 사람은 빠른 사람이어야 한다.

 

두 명의 사람이 건널 때 가장 빠른 경우는

    가장 빠른 두 사람이 함께 건너는 것

두 명의 사람이 건널 때 가장 느린 경우는

    가장 느린 사람이 한 명이라도 있을 경우

 

이 말은 가장 느린 사람이 건너는 시간을 좌우하기 때문에 가장 느린 사람과 같이 가는 사람이 아무리 빠르더라도 아무런 소용이 없을 것이다.

그렇다면 가장 빠른 사람이 가장 느린 두 사람을 차례로 데려다 주는 것보다 가장 느린 두 사람이 동행하면 훨씬 시간적으로 이득이다.

그렇다고 처음부터 가장 느린 두 사람을 보내면 안된다. 왜냐하면 두 사람 중 한 명은 결국 손전등을 들고 돌아와야 하기 때문.

 

정리해보자면 가장 빠른 두 사람이 길을 건너고, 둘 중 한 사람이 돌아온다.

이후 가장 느린 두 사람이 길을 건너고, 섬에 남아있던 빠른 사람이 먼저 건너간 빠른 사람들 데리러 돌아온다.

최종적으로 가장 빠른 두 사람이 길을 건너면서 종료된다.

 

사람이 더 많은 경우에도 고려해야 할 점은

• 속도가 비슷한 사람끼리 건너야 한다
• 가장 느린 두 사람을 섬으로 보냈다면, 그 두 사람을 제외한 새로운 상황으로 생각하면 된다.
• 핵심은 가장 빠른 두 사람이 손전등을 전달해 주는 역할을 하는 것과
• 가장 느린 두 사람을 단계별로 제거해 나가는 재귀 문제로 생각된다
• 마지막으로 3명이 남았다면 가장 빠른 사람이 나머지 두 명을 데려다 주는 경우가 가장 빠르다

#include<stdio.h>

int left = 4;   // 남은 사람 수
int hIndex = 0; // Index of History
int steps = 0;  // 최소 이동 시간

void crossingBridge(int* arr, int start, int end, int* history);

int main(void) {
    int input[5] = { 4, 1, 2, 5, 10 };
    int history[30];
    crossingBridge(input, 1, input[0], history);
}

void crossingBridge(int* arr, int start, int end, int* history) {
    if (left < 4) {
        // 3명 남은 경우
        if (left == 3) {
            // 가장 빠른 두 명 보내기
            *(history + hIndex++) = arr[start];
            *(history + hIndex++) = arr[start + 1];
            *(history + hIndex++) = 0;
            // 가장 빠른 한 명 돌아옴
            *(history + hIndex++) = arr[start];
            *(history + hIndex++) = 0;
            // 가장 느린 한 명과 가장 빠른 한 명 이동
            *(history + hIndex++) = arr[start];
            *(history + hIndex++) = arr[3];
            *(history + hIndex++) = 0;
            left -= 3;
            steps += arr[start] + arr[start + 1] + arr[3];
        }
        // 2명 남은 경우
        if (left == 2) {
            *(history + hIndex++) = arr[start];
            *(history + hIndex++) = arr[start + 1];
            *(history + hIndex++) = 0;
            left -= 2;
            steps += arr[start + 1];
        }
        // history 출력
        printf("%d\n", steps);
        for (int i = 0; i < hIndex; i++) {
            if (history[i] == 0)
                printf("\n");
            else {
                printf("%d ", history[i]);
            }
        }
        return; // 재귀 함수 종료
    }
    // 가장 빠른 두 명 보내기
    *(history + hIndex++) = arr[start];
    *(history + hIndex++) = arr[start + 1];
    *(history + hIndex++) = 0;
    left -= 2;
    steps += arr[start + 1];
    // 가장 빠른 한 명 돌아옴
    *(history + hIndex++) = arr[start];
    *(history + hIndex++) = 0;
    left += 1;
    steps += arr[start];
    // 가장 느린 두 명 건너감
    *(history + hIndex++) = arr[end - 1];
    *(history + hIndex++) = arr[end];
    *(history + hIndex++) = 0;
    left -= 2;
    steps += arr[end];
    // 두번째로 빠른 한 명 돌아옴
    *(history + hIndex++) = arr[start + 1];
    *(history + hIndex++) = 0;
    left += 1;
    steps += arr[start + 1];
    // 재귀 처리
    end -= 2;
    crossingBridge(arr, 1, end, history);
}