[부스트 코딩 뉴비 챌린지 2020] week4_미션03

✔︎ 미션 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. 핵심 개념
#정렬알고리즘

 

* 본 문제의 경우 문제를 푸는데 도움이 되는 힌트가 있습니다. 알고리즘의 경우 방법을 직접 고민해보고 찾는 것이 중요합니다. 때문에 고민을 하시다가 도저히 풀 수가 없을때 아래의 힌트를 참고해주시길 바랍니다.

 

-> '         ' 사이를 마우스로 블록을 하면 힌트가 나옵니다.

 '각 사람들이 다리를 건너는 시간에 따라서 예)에 있는 출력값과 같은 방법으로 다리를 건너는 것이 최선이 아닌 경우도 있습니다. 어떤 경우에 그렇게 되는지, 그리고 그 때는 어떤 방법으로 다리를 건너는 것이 최선인지 생각해봅시다'

 

---

(1) 한 번에 최대 2명이 이동 가능하다.

(2) 손전등이 하나 뿐이므로, 한 번 다리를 건너면 한 사람은 다시 손전등을 가지고 돌아와야 한다.

(3) 이동수가 최소여야 한다.

 

예시처럼 속도가 1 2 5 10인 4명의 사람들이 다리를 건너게 되는 경우, 

1 2 5 10 -> X

5 10      -> 1 2             : 1 2가 다리를 건넌다 (+2)

1 5 10   <- 2                : 1이 손전등 가지고 다시 돌아온다 (+1)

1          -> 2 5 10         : 5 10이 다리를 건넌다 (+10)

1 2       <- 5 10            : 2가 손전등 가지고 다시 돌아온다 (+2)

           -> 1 2 5 10       : 1 2가 다리를 건너서 다시 돌아온다 (+2)

따라서 2+1+10+2+2 = 17. 총 17시간으로 가장 짧은 시간 안에 돌아올 수 있다.

 

아니면 가장 큰 수와 가장 작은 수가 돌아오는 방법도 있지 않을까? 해서 다른 방법도 생각해보았다.

1 2 5 10 -> X

2 5        -> 1 10          : 1 10이 다리를 건넌다(+10)

1 2 5     <- 10             : 1이 손전등 가지고 다시 돌아온다(+1)

1          -> 2 5 10        : 2 5가 다리를 건넌다 (+5)

1 2        <- 5 10          : 2가 손전등 가지고 다시 돌아온다(+2)

            -> 1 2 5 10     : 1 2가 다리를 건넌다 (+2)

이렇게 하면 10+1+5+2+2 = 20. 더 많은 시간이 걸린다. 따라서 위의 경우가 최소의 값이 나오므로 내가 생각한 방법은 버리자.

 

만약 첫 번째 방법으로 1 2 3 4 5 6 7이 다리를 건넌다고 한다면,

1 2 3 4 5 6 7 -> X

3 4 5 6 7      -> 1 2              (+2) : 1 2 건넘

1 3 4 5 6 7    <- 2                (+1) : 1이 손전등 가지고 돌아옴

1 5 6 7         -> 2 3 4           (+4) : 3 4 건넘

1 2 5 6 7      <- 3 4              (+2) : 2가 손전등 가지고 돌아옴

1 2 7           -> 3 4 5 6         (+6) : 5 6이 건넘

1 2 3 7        <- 4 5 6            (+3) : 3이 손전등 가지고 돌아옴

1 2              -> 3 4 5 6 7      (+7) : 3 7이 건넘

1 2 3           <- 4 5 6 7         (+3) : 3이 손전등 가지고 돌아옴

1                -> 2 3 4 5 6 7    (+3) : 2 3이 건넘

1 2             <- 3 4 5 6 7       (+2) : 2가 손전등 가지고 돌아옴

                 -> 1 2 3 4 5 6 7  (+2) : 1 2가 건넘

2+1+4+2+6+3+7+3+3+2+2 = 총 35 시간이 걸린다.

 

그렇다면 이제 첫 번째 방법을 해석해보자.

 

 

 

 

 

먼저 다리는 [a[0] a[1]], [a[2] a[3]], ... 쌍으로 건너게 된다. 그리고 총 시간인 sum에는 a[1], a[3], a[5], ... 만큼 더해질 것이다. 따라서, 

int sum;


for(int i = 0; i < LENGTH ; i+2){
	printf("%d %d", a[i], a[i+1]);
	sum += a[i+1];
}

 

와 같이 작성할 수 있다.

 

다음은 다리를 건넌 수 중에서 가장 작은 수가 돌아와야 한다. 처음에는 a[0], 그다음은 a[1], 다음은 a[2],... 순으로 돌아와야 한다.

 

 

 

다리는 [1 2], [5 10]쌍으로 무조건 건너게 된다. 즉, a[1]+a[3]+a[5]+...만큼 더해질 것이므로

int sum;

for (int i = 0; i < LENGTH; i ++) {
	if(i%2 == 1){
		sum += a[i];
	}
}

와 같이 작성할 수 있다.

여기서 i가 짝수인 경우는 i/2만큼, 홀수인 경우는 i/2+1만큼 다시 원래 자리로 돌아오게 된다. 이때 돌아오는 수는 배열에서 가장 작은 수이다. 따라서

int limit;

if(i%2 == 0){
    limit = i/2;
}else{
    limit = i/2 + 1;
}
for(int i = 0; i < limit; i++){
    sum += a[i];
}

가 된다.

또 돌아온 숫자들은 다시 다리를 건너서 간다. 이때 홀수인 경우, a[0]~a[i/2+1], 짝수인 경우 a[0]~a[i/2]만큼 돌아오는데 이의 홀수 배열들만 sum에 더하게 된다.

for(int i = 0; i < limit; i++){
    if(i%2 == 1){
        sum += a[i];
    }
}

 

 

이를 실행하는 프로그램을 만드려면 코드를 어떻게 작성하면 좋을까? 먼저 의사코드(pseudo code)로 작성해보자.

 

1. 입력값인 배열 a를 오름차순으로 정리한다.

2. 배열 a에서 sum += a[1]을 하고 a[0]과 a[1]을 배열b로 보낸다.

3.