우선 가장 빠른 2명을 고릅니다. 그리고 그 2명 중 한 명이라도 기숙사에 가 있다면 가장 느린 둘을 보내고, 2명이 모두 현관에 있다면 가장 빠른 둘을 보냅니다. 또한 돌아올 때는 기숙사에 있는 학생 중 가장 빠른 학생을 데리고 옵니다.

while __name__ == '__main__':
    e = sorted(list(int(x) for x in input('>>>').split())[1:])
    a = e[:]; b = []; result = 0

    while 1:
        if len(a) == 2:
            result += max(a)
            break
        a.sort()
        if a[:2] == e[:2]:
            b += a[:2]
            result += max(a[:2])
            a = a[2:]
        else:
            b += a[-2:]
            result += max(a[-2:])
            a = a[:-2]

        b.sort()
        a += b[0:1]
        result += b[0]
        b = b[1:]

    print(result)

파이썬 3.5.1 64

이 문제에 관한 흥미로운 페이퍼가 있습니다

링크 .

저는 여기에 서술한 알고리즘을 기반으로 코드를 짰어요. C++입니다.

// By Minsuk Kim (Luke)
// Code that solves 2015 Stanford Local Programming Contest Problem G  
// Problem link: https://open.kattis.com/contests/onyyqy/problems/safepassage 
// Variation of the Bridge and Torch problem. 
// Refer to this link for a theoretical treatment of this problem: 
// http://page.mi.fu-berlin.de/rote/Papers/pdf/Crossing+the+bridge+at+night.pdf
// Maximum input size is only 15 so no need to worry about TLE. 
#include <iostream>
#include <cstdlib>
#include <vector> 
#include <algorithm> 
#include <climits>
using namespace std;  

vector<int> storeInfo; 
vector<int> storeVal; 
int ans = INT_MAX; 

void calc(){
    int N = storeInfo.size(); 
    for (int i = 0; i <= N/2 - 1; i++){
        int val = 0; 
        val += (N-2-i)*storeInfo[0] + (2*i+1)*storeInfo[1]; 
        for (int j = 3; j <= N; j++){
            val += storeInfo[j-1]; 
        }
        for (int j = 1; j <= i; j++){
            val -= storeInfo[N+1-2*j-1]; 
        }
        storeVal.push_back(val); 
    }
    return;     
}

void findMin(){
    for (vector<int>::size_type i = 0; i < storeVal.size(); i++){
        ans = min(ans,storeVal[i]); 
    }   
}

int main(){
    int n; 
    cin >> n; 
    for (int i = 0; i < n; i++){
        int num; 
        cin >> num; 
        storeInfo.push_back(num);
    }
    sort(storeInfo.begin(),storeInfo.end());
    calc(); 
    findMin();
    cout << ans << endl;
    return 0; 
}

이 코드는 일단 kattis에 있는 체점 데이터는 모두 통과합니다.

Ruby

빠른 둘로 가장 느린 둘을 이동시키는 시간을 한 사이클로 두면 수식으로 일반화 가능. 최초 입력값 정렬한 뒤 수식에 대입. a,b를 가장 빠른 둘, rest를 나머지라 할 때, 전체이동시간 = (a x a단독이동횟수) + (b x b의 이동횟수) + (느린 멤버 둘씩 이동하는 시간의 총합)

def safe_time(students, times=students.split.map(&:to_i))
  size,(a,b,*rest) = times.shift, times.sort
  rest[0] ? a*(size-1)/2 + b*(size-1 - size%2) +
            rest.reverse.each_slice(2).map(&:first).sum : b||a
end

Test

expect( safe_time("2 15 5") ).to eq 15
expect( safe_time("4 1 2 7 10") ).to eq 17
expect( safe_time("5 12 1 3 8 6") ).to eq 29 

Output

safe_time("4 1 2 7 10") #=> 17

C로 했습니다. 일단 배열에 담아서 소팅을 먼저 시도를 하구요 서로서로 이동하기위해서 젤 빠른사람과 그다음번째로 빠른사람을 활용을 해야합니다. 2명만 있을경우 둘중 느린사람값, 3명만있을경우 가장느린사람 + 가장빠른사람이 복귀하는경우 + 두번째로 빠른사람 나머지경우에는 항상 4번의 이동이 있는데요 이때 2번째로 빠른사람 + 1번째빠른사람 + 가장느린사람 + 2번째 빠른사람. 2명을 이동했으니깐 n = n-2를 했습니다!

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<malloc.h>

void sort(int a[], int n)
{
    int max_index = 0;
    bool flag = true;
    while (flag)
    {
        flag = 0;
        for (int i = 0; i < n-1; i++)
        {
            if (a[i] > a[i+1])
            {
                int temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
                flag = true;
            }

        }
        n--;
    }

}
int calculate(int a[], int n)
{
    sort(a, n);
    int sum = 0;

    while (n > 1)
    {
        if (n == 2)
            sum += a[1];
        else if (n == 3)
            sum += a[2] + a[0] + a[1];
        else
            sum += a[1] + a[0] + a[n-1] + a[1];
        n -= 2;
    }
    return sum;

}
int main()
{
    int n = 0;

    scanf(" %d", &n);
    int* a = (int*)malloc(sizeof(int) * n);

    for (int i = 0; i < n; i++)
        scanf(" %d", &a[i]);

    printf("%d", calculate(a, n));

}

nums=input().split()
if int(nums[0])!=(len(nums)-1):
    print("wrong number!")
else:
    nums.pop(0)
    a=[]
    for i in nums:
        a.append(int(i))
    a.sort()
    times=0
    min1=a[0]
    min2=a[1]
    a.pop(0)
    a.pop(0)
    times+=min2
    while len(a)!=0:
        if len(a)!=1:
            times+=min1+a[-1]+min2+min2
            a.pop(-1)
            a.pop(-1)
        else:
            times+=min1+a[-1]
            a.pop(-1)
    print(times)

실제 Data를 Swap 해서 처리, 효율적이지는 못하네요

#include <iostream> 
#include <list> 
#include <algorithm>
using namespace std;

list<int> startInfo;
list<int> goalInfo;
int spandTime = 0;
int fastest, secondFastest;
bool selectedToggle = false;

int moveToGoal(int a, int b){   
    list<int>::iterator findIterA = find(startInfo.begin(), startInfo.end(), a);    
    goalInfo.push_back(a);      
    startInfo.erase(findIterA);
    list<int>::iterator findIterB = find(startInfo.begin(), startInfo.end(), b);
    goalInfo.push_back(b);
    startInfo.erase(findIterB); 
    spandTime += max(a, b);
    return startInfo.size();
}

int moveToStart(int a){
    list<int>::iterator findIterA = find(goalInfo.begin(), goalInfo.end(), a);
    startInfo.push_back(a);
    spandTime += a;
    goalInfo.erase(findIterA);
    return startInfo.size();
}

//PeekType 0:fastest , 1:SecondFastest , 2 BestPeek
int peekStudent(int peekType , list<int>& someWhere) {
    someWhere.sort();
    int result = 0;
    switch (peekType){
        case 0:
            result = someWhere.front();
            break;
        case 1: {
                std::list<int>::iterator it = someWhere.begin();
                if (it != someWhere.end()) {
                    it++;               
                }
                result = *it;       
            }           
            break;
        case 2: {
            list<int>::iterator findIterF1 = find(startInfo.begin(), startInfo.end(), fastest);
            list<int>::iterator findIterF2 = find(startInfo.begin(), startInfo.end(), secondFastest);
            bool superUnitTwo = false;
            bool superUnitOne = false;

            if (findIterF1 != startInfo.end() && findIterF2 != startInfo.end())
                superUnitTwo = true;

            if (findIterF1 != startInfo.end() || findIterF2 != startInfo.end())
                superUnitOne = true;

            if (superUnitTwo) {
                if (selectedToggle == true) {
                    selectedToggle = false;
                    result = *findIterF2;
                }
                else {
                    selectedToggle = true;
                    result = *findIterF1;
                }
            }
            else if (superUnitOne) {
                if (selectedToggle == true) {
                    selectedToggle = false;
                    std::list<int>::iterator it = someWhere.end();
                    it--;
                    it--;
                    result = *it;
                }
                else {
                    selectedToggle = true;                  
                    result = someWhere.back();
                }
            }
        }
        break;
    }
    return result;
}

int main(){ 
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        startInfo.push_back(num);
    }

    int remainStudent = startInfo.size();
    //제일빠른놈 두놈 peek
    fastest = peekStudent(0, startInfo);
    secondFastest = peekStudent(1, startInfo);

    while (remainStudent > 0)
    {       
        int stA = peekStudent(2, startInfo);    //Best Peek
        int stB = peekStudent(2, startInfo);
        moveToGoal(stA, stB);
        if (startInfo.size() > 0) {
            int stC = peekStudent(0, goalInfo); //제일 빠른 놈이 복귀
            moveToStart(stC);
        }
        remainStudent = startInfo.size();
    }
    cout << spandTime;
    return 0;
}

시간이 가장 적게 걸리는 사람부터 가장 오래걸리는 사람 순으로 A, B, C... 로 이름을 붙여서 인물들의 움직임을 출력했습니다.

def printStatus(left, right, total, str):
    print ('----- ' + str + ' -----')
    print ("좌측:", left, "\t우측:", right, "\t총 걸린 시간 :", total )


def move(ori,oriTime,index,term,termTime,):
    term.append(ori.pop(index))
    termTime.append(oriTime.pop(index))
    term.sort()
    termTime.sort()


def cross(left, leftTimes, right, rightTimes, total):

    if (len(right)) == 0:
        return

    # 두명 이하 남았을때
    elif (len(right)) <= 2 :
        total += rightTimes[-1]
        str = ''
        if (len(right) == 1):
            str = right[0] + " 좌측으로 이동"
        else:
            str = right[0] + " & " + right[1] + " 좌측으로 이동"

        while len(right)>0:
            move(right,rightTimes,0,left,leftTimes)

        printStatus(left,right,total,str)
        return

    # 세명 남았을때
    elif (len(right)) == 3 :
        # step 1
        total += rightTimes[-1]
        str = right[0] + " & " + right[-1] + " 좌측으로 이동"
        move(right, rightTimes, 0, left, leftTimes)
        move(right, rightTimes, -1, left, leftTimes)
        printStatus(left, right, total, str)

        # step 2
        total += leftTimes[0]
        str = left[0] + " 우측으로 복귀"
        move(left,leftTimes,0,right,rightTimes)
        printStatus(left, right, total, str)

        # step 3
        cross(left, leftTimes, right, rightTimes, total)
        return

    # 네명 이상 남았을때
    else :
        # step 1
        total += rightTimes[1]
        str = right[0] + " & " + right[1] + " 좌측으로 이동"
        move(right, rightTimes, 0, left, leftTimes)
        move(right, rightTimes, 0, left, leftTimes)
        printStatus(left, right, total, str)

        # step 2
        total += leftTimes[0]
        str = left[0] + " 우측으로 복귀"
        move(left, leftTimes, 0, right, rightTimes)
        printStatus(left, right, total, str)

        # step 3
        total += rightTimes[-1]
        str = right[-2] + " & " + right[-1] + " 좌측으로 이동"
        move(right, rightTimes, -2, left, leftTimes)
        move(right, rightTimes, -1, left, leftTimes)
        printStatus(left, right, total, str)

        # step 4
        total += leftTimes[0]
        str = left[0] + " 우측으로 복귀"
        move(left, leftTimes, 0, right, rightTimes)
        printStatus(left, right, total, str)

        # step more
        cross(left, leftTimes, right, rightTimes, total)


nums=input('Numbers:').split()

total = int(nums[0])
times = []
for i in nums[1:]:
    times.append(int(i))

print('총인원 :', total)
times.sort()
print(times)

names = []
for i in range(len(times)):
    names.append(chr(ord('A')+i))
print(names)

left = []
right = names

#print('----- Start -----')
printStatus(left,right,0,'Start')

cross(left, [], right, times, 0)

답변 감사합니다.

덕분에 코드 수정할 수 있었고 잘 이해못한 알고리즘도 이해하게 됐습니다~

#include <stdio.h>
#include <stdlib.h>

int sort(int* time, int length);
int* cal(int* arr ,int count);
int sum = 0;

void main(void) {
    int n;
    int count = 0;
    int input[16];
    scanf("%d",&n);
    for(int i = 0 ; i < n; i++) {
        scanf("%d",&input[i]);
    }

    int* time = (int*) malloc (sizeof(int) * n);
    time = input;

    n = sort(time ,n);

    if(n%2 != 0) {
        n--;
        sum = time[n/2] + time[0];
    }
    int* temp = (int*) malloc (sizeof(int) * n);
    temp = time;

    int j = 0;
    for(int i =0; i < n; i++) {
        if(n/2 == i) {
            j++;
            temp[i] = time[j];
        } else 
            temp[i] = time[j];

        j++;

    }

    for(int i = 0 ; i < (n/2); i++) {
        temp = cal(temp, n);
    }
    printf("\n%d\n",sum);
}
int* cal(int* arr ,int n) {
    int* temp = (int*) malloc (sizeof(int) * n) ;
    for(int i = 0 ; i < n ; i++) {
        if(i < (n/2)) {
            sum = sum + arr[((i+1)*2)-1];
            if(arr[2]  != 0 && n>2)
                sum = sum + arr[i];
            temp[i]  =  arr[i];
        }
        else {
            temp[i]  =  0;
        }
    }
    return temp;
}

int sort(int* time, int length) {
    int temp;
    for(int i = 0 ; i < (length-1) ; i++) {
        for(int j = 0 ; j < (length-1) ; j++) {
            if(time[j] > time[j+1]) {
                temp = time[j+1];
                time[j+1] = time[j];
                time[j] = temp;
            } 
        }
    }
    return length;
}

ptyhon 2.7입니다.

s_list=[]
d_list=[]
tmp=[]

def Get_num_pos(n):
    num=1
    for i in range(0,n-1):
        num*=10
    return num

def Change_type(n):
    num,length=0,len(n)
    for j in n:
        num+=(ord(j)-ord('0'))*Get_num_pos(length)
        length-=1
    return num

def Safe_Passage(n):
    Time=0
    c,mi,mj,b=0,0,0,0
    s=raw_input().split()
    for i in s:
        s_list.append(Change_type(i))

    while(len(s_list)!=0):
        if(b==0):
            if(c==0):
                mi=min(s_list)
                s_list.remove(mi)
                mj=min(s_list)
                s_list.remove(mj)
                c=1
            else:
                if(len(s_list)%2==0):
                    mi=max(s_list)
                    s_list.remove(mi)
                    mj=max(s_list)
                    s_list.remove(mj)
                else:
                    mi=max(s_list)
                    mj=min(s_list)
                    s_list.remove(mi)
                    s_list.remove(mj)
            Time+=max(mi,mj)              
            d_list.append(mi)
            d_list.append(mj)

        else:
            c=min(d_list)
            s_list.append(c)
            d_list.remove(c)
            Time+=c
        b=not b

    print Time

Safe_Passage(5)

참고 많이 했는데 쉽지 않네요 더 간결하고 쉽게 하는 방법을 생각해야겠네요..

len_, *in_ = map(int, input(":").split(' '))
in_.sort()

min_ = {in_[0], in_[1]}
t = 0
out_ = []
while in_:
    if min_ & set(out_):
        p = [in_.pop()]
        if in_:
            p += [in_.pop()]
    else:
        p = [in_.pop(0)]
        if in_:
            p += [in_.pop(0)]
    t += max(p)
    out_ += p
    out_.sort()
    if in_:
        p = out_.pop(0)
        t += p
        in_.insert(0, p)

print(t)

Python 3.5.2에서 작성하였습니다.

```{.java}

import java.util.Arrays; import java.util.Scanner;

public class Safe_Passage {

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int time = 0;
    int num = scan.nextInt();
    int[] student = new int[num];
    for(int i = 0; i < num; i++){
        student[i] = scan.nextInt();

    }
    Arrays.sort(student);

    do{
        if(num == 1)
            time += student[0];
        else if(num == 2)
            time += student[1];
        else if(num == 3)
            time += student[0]+student[1]+student[2];
        else
            time += cross_route(student, num);
        num -= 2;
    }while(num > 1);

    System.out.println(time);
}

private static int cross_route(int[] student, int num) {
    int time = 0;
    time += student[1]+student[0]+student[num-1]+student[1];
    return time;
}

}

```> 빠른 순서대로 a,b,c,d,e,f 있다고 한다면 (a,b)를 보내고 a를 다시 보냅니다. 그리고 제일 느린 (e,f)를 보내고 기숙사에 있던 b를 다시 정문으로 돌려 보냅니다. 그러면 a,b,c,d 이렇게 4명이 남게 되는데 원래 멤버에서 제일 느린 2명이 빠진 멤버가 됩니다. 이 과정은 4명 이상부터 적용할 수 있습니다. 이 과정을 한 번의 method로 만들고 남은 사람의 숫자가 1,2,3이 될 때까지 반복 후 1,2,3이 되면 마무리 합니다.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

import static java.lang.System.in;

/*
* 주어진 입력을 오름차순으로 정렬하고 2개의 데크를 이용 하면 가능 할 듯
* */
public class SafePassage {
    public static void main(String[] args) {
        Scanner sc = new Scanner(in);
        int n = sc.nextInt();

        List<Integer> d = new ArrayList<>();
        List<Integer> e = new ArrayList();

        for (int i = 0; i < n; i++) {
            d.add(sc.nextInt());
        }

        d = d.stream().sorted().collect(Collectors.toList());

        Integer k = 0;

        while (true) {
            Integer a, b, c;
            a = d.remove(0);
            b = d.remove(0);
            e.add(a);
            e.add(b);
            k = k + (a > b ? a : b);

            if (d.size() == 0) break;

            d = d.stream().sorted(Comparator.reverseOrder()).collect(Collectors.toList());
            e = e.stream().sorted().collect(Collectors.toList());

            c = e.remove(0);
            d.add(c);
            k = k + c;
        }
        System.out.println(k);
    }
}

// 투명 망토 - C#
// 알고리즘은 가장 가벼운 2명이 먼저 가고, 제일 가벼운 사람(이하 1호)가 돌아옵니다.
// 그 다음엔 가장 무거운 2명이 가고, 2호가 돌아옵니다.
// 이후에는 1, 2호가 남을 때까지 1호가 무거운 사람들을 하나씩 옮깁니다. 
// 마지막에는 1, 2호가 모두 기숙사에 도착합니다.
using System;
namespace CloakofInvisibility
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Ready >>>");
            string input = Console.ReadLine();
            int num = int.Parse(input.Split(' ')[0]);
            int[] time = new int[num];
            for (int i = 1; i < 16; i++)
                try { time[i - 1] = (int.Parse(input.Split(' ')[i])); }
                catch { break; }
            Array.Sort(time); int sum = 0;
            if (num == 1)
                sum += time[0];
            else if (num == 2)
                sum += time[1];
            else
            {
                sum += time[1] + time[0];
                if (num == 3)
                    sum += time[2];
                else
                {
                    sum += time[num - 1] + time[1];
                    for (int i = 4; i < num; i++)
                        sum += time[num - i + 1] + time[0];
                    sum += time[1];
                }
            }
            Console.WriteLine(sum);
        }
    }
}

import java.util.Arrays;
import java.util.Scanner;

public class test02 {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int num = s.nextInt();
        int student[] = new int[num];

        for (int i = 0; i < num; i++) {
            student[i] = s.nextInt();
        } // n개의 숫자를 배열에 저장
        Arrays.sort(student);


        int time=0;
        time=route(student,num,time);

        System.out.println(time);

    }

    public static int route(int[] student,int num,int time) {
        if(num>=4) {
            time+=student[1]+student[0]+student[num-1]+student[1];
            //System.out.println(time);
            return route(student,num-2,time);   
        }
        else if(num==3) {
            time+=student[0]+student[1]+student[2];
        }
        else if(num==2) {
            time+=student[1];
        }
        return time;
    }

}

정문으로 돌아올 떄는 항상 기숙사에서 가장 빠른 사람이 오게 됩니다.

정문에서는 가장 빠른 2명 또는 가장 느린 2명이 기숙사로 이동하는 두 가지 경우가 있습니다.

2명 뽑을 때 제대로 하면 코드가 너무 지저분해져서 그냥 sort를 썼습니다.

def mintime(gate, dom):
    dom.sort()    
    if dom:
        bt = dom[0]
        gate.append(dom.pop(0));
    else:
        bt = 0

    if len(gate) <= 2:
        return bt + max(gate)

    gate.sort() 
    return min(
        bt + max(gate[:2]) + mintime(gate[2:], dom + gate[:2]),
        bt + max(gate[-2:]) + mintime(gate[:-2], dom + gate[-2:])
        )


data = '2 15 5\n4 1 2 7 10\n5 12 1 3 8 6'
data = list(map(int, data.split()))
while data:
    N = data[0]
    print(mintime(data[1:N+1], []))
    data = data[N+1:]

inp = '5 12 1 3 8 6'.split()

n = int(inp[0])
gate = sorted([int(i) for i in inp[1:]])
fast = gate[:2]
dorm = []
time = 0

while 1:
    # dorm <- gate
    if fast[0] in dorm or fast[1] in dorm:
        gate, [m1, m2] = gate[:-2], gate[-2:]
    else:
        [m1, m2], gate = gate[:2], gate[2:]
    time += max(m1, m2)
    dorm += [m1, m2]
    dorm.sort()

    # dorm -> gate
    if gate:
        m1 = dorm.pop(0)
        time += m1
        gate.append(m1)
        gate.sort()
    else:
        break

print(time)

Java 입니다.

import java.util.Collections; import java.util.LinkedList; import java.util.Scanner;

public class level_3_safe_passage {

public static void main(String[] args) {

    LinkedList<Integer> start = new LinkedList<Integer>(); // 시작점.
    LinkedList<Integer> end = new LinkedList<Integer>(); // 도착점.
    int time = 0; // 총 시간.

    Scanner sc = new Scanner(System.in);
    System.out.println("학생의 수를 입력하세요.");
    int number = sc.nextInt();
    System.out.println("학생들의 속도를 차례로 입력하세요.");      
    for(int i = 0; i < number; i++) // start 리스트에 학생들 속도 입력.
    {
        start.add(sc.nextInt());
    }
    sc.close();

    int a = Collections.min(start); // start 리스트에서 가장 빠른 학생을 가져옴.
    end.add(a); // end 리스트에 start 학생 입력.
    start.remove(Collections.min(start)); // start 리스트에서 학생 삭제.

    a = Collections.min(start); // start 리스트에서 두번째로 빠른 학생을 가져옴.
    end.add(a); // end 리스트에 start 두번째 학생 입력.
    start.remove(Collections.min(start)); // start 리스트에서 두번째 학생 삭제.
    time = time + a;

    while(true) // 편의를 위해 무한루프.
    {
        a = Collections.min(end); // 가장 빠른 한명 ←
        start.add(a);
        end.remove(Collections.min(end));
        time = time + a;

        for(int i = 0; i < 2; i++) // 가장 느린 두명 →
        {
            a = Collections.max(start);
            end.add(a);
            start.remove(Collections.max(start));

            if(i == 0) // 두명중에서 가장 느린 사람 시간만 추가함.
            {
                time = time + a;
            }
        }
        if(start.size() == 0) // start 리스트의 사이즈가 0 이면 끝냄.
        {
            break;
        }       
    }
    System.out.println("모든 학생이 안전하게 통과하는데 걸린 시간 : " + time);
}

}

// List 처음 써봤는데 배열과는 다른 매력이 있네요.

파이썬 3.6

def passagetime(data):
    home,passage,time = [],[],0
    gate = [int(i) for i in data]
    while gate:
        if len(gate) <= 2:
            passage.extend(gate)
            time += max(passage)
            break
        if home:
            gate.sort(reverse=True)
# 정문에 남은 사람 중 가장 느린 사람이 기숙사에 도착한 사람 중 가장 빠른 사람보다 빠르다면,
# 이번에 이동하는 사람중  빠른 사람이 돌아와야 하므로, 남은 사람중 가장 느린사람과 빠른 사람이 짝을지어 이동한다. 
            if max(gate) < min(home):
                passage.append(min(gate))
                passage.append(max(gate))
# 그 외의 경우( ex>정문에 남은 사람 중 가장 빠른 사람이 기숙사에 도착한 사람 중 가장 빠른 사람보다 느린 경우),
# 정문에 남은 사람 중 가장 느린 사람 두 사람이 짝을지어 이동한다.
            else:
                for i in gate:
                    passage.append(i)
                    if len(passage) == 2:
                        break
            gate.remove(passage[0])
            gate.remove(passage[1])
            time += max(passage)
            home.extend(passage)
            passage = []
            time += min(home)
            passage.append(min(home))
            home.remove(min(home))
            gate.extend(passage)
            passage = []
        else:
            gate.sort()
# 최초 가장 빠른 사람 두 사람이 기숙사로 돌아옵니다.
            for i in gate:
                passage.append(i)
                if len(passage) == 2:
                    break
            gate.remove(passage[0])
            gate.remove(passage[1])
            time += max(passage)
            home.extend(passage)
            passage =[]
            time += min(home)
# 기숙사에서 돌아올 때 기숙사에 있는 사람 중 가장 빠른 사람 한 명이 돌아옵니다.
            passage.append(min(home))
            home.remove(min(home))
            gate.extend(passage)
            passage =[]
    print(time)    

if __name__ == "__main__":
    data = input('').split()
    passagetime(data)

*결과값

5 15
15

1 2 7 10
17

12 1 3 8 6
29

인원을 입력하지 않고 처음부터 이동하는데 걸리는 시간을 입력받습니다.

def passage(a):
    time = 0
    a.sort()
    if len(a) == 0:
        time += 0
    elif len(a) == 1:
        time += a[0]
    elif len(a) == 2:
        time += a[1]
    elif len(a) == 3:
        time += sum(a)
    else:
        time += passage(a[:-2]) + min(a[1]+a[0]+a[-1]+a[1], a[-2]+a[0]+a[-1]+a[0])
    return time
a = list(map(int, input().split()))
print(passage(a))

arr = [int(i) for i in input().split()]
arr.sort()
t = 0

while len(arr) > 3:
    t += arr[0]+arr[1]+arr[-1]+arr[1]
    arr.pop()
    arr.pop()
if len(arr) == 1: t += arr[0]
elif len(arr) == 2: t += arr[-1]
elif len(arr) == 3: t += sum(arr)

print(t)