The Bridge and Torch Problem

논문, 참고1, 참고2

1. Python

import sys
def main():
    # 이곳에 소스코드를 작성하세요.
    # Python3 만 지원됩니다.
    # pass는 삭제해도 됩니다.
    
    
    t = int(sys.stdin.readline())
    #f = open('sample_input.txt', 'r')
    #t = int(f.readline())

    result = []


    def cross(s):
        s.sort()                                   
        if len(s)>3:                              
            a = s[0]+s[-1]+min(2*s[1],s[0]+s[-2]) 
            return  a + cross(s[:-2])                 
        else:
            return sum(s[len(s)==2:])             


    for i in range(t):
      n = int(sys.stdin.readline())
      #n = int(f.readline())

      data = list(map(int,sys.stdin.readline().split()))
      #data = list(map(int,f.readline().split()))

      min_distance = cross(data)
      result.append(min_distance)

    for i in range(t):
      print(f'#{i+1} {result[i]}')



    
main()

2. Java

class Program
{
    public static int TotalTime(List<int> band, int n)
    {
        if (n < 3)
        {
            return band[n - 1];
        }
        else if (n == 3)
        {
            return band[0] + band[1] + band[2];
        }
        else
        {
            int temp1 = band[n - 1] + band[0] + band[n - 2] + band[0];
            int temp2 = band[1] + band[0] + band[n - 1] + band[1];

            if (temp1 < temp2)
            {
                return temp1 + TotalTime(band, n - 2);
            }
            else if (temp2 < temp1)
            {
                return temp2 + TotalTime(band, n - 2);
            }
            else
            {
                return temp2 + TotalTime(band, n - 2);
            }
        }
    }

    static void Main(string[] args)
    {
        // change the no of people crossing the bridge
        // add or remove corresponding time to the list
        int n = 4; 

        List<int> band = new List<int>() { 1, 2, 5, 10 };

        band.Sort();

        Console.WriteLine("The total time taken to cross the bridge is: " + Program.TotalTime(band, n));
        Console.ReadLine();
    }
}