Safe Passage (2015 ACM-ICPC North American Qualifier Contest)

출처 : https://open.kattis.com/problems/safepassage

밤늦게까지 놀다온 학생들이 선생님들을 피해 학교 정문에서 기숙사까지 들키지 않고 가려고한다.학생들은 투명 망토가 있는데 망토는 한번에 최대 두사람씩 이용할 수 있다. 각 학생들은 학교 정문에서 기숙사까지 가는데 걸리는 시간이 주어지는데 만약 속도가 다른 두 사람이 망토를 같이 쓰고 정문에서 기숙사까지 간다면 더 빨리 갈 수 있는 사람이 더 느린사람의 페이스에 맞춰서 가야한다. 이런식으로 최대 두명씩 망토를 쓰고 이동가능하다고할때 최대한 빨리 기숙사에 도착하려고한다. 예를 한번 들어보자. 학생 4명 (A,B,C,D)가 있다고하고 각각 정문에서 기숙사까지 1분,2분,7분,10분이 걸린다고하면, 4명모두 기숙사까지 최대한 빨리 가는 방법은 다음과 같다:

A,B가 망토를 쓰고 정문에서 기숙사로 간다 (2분걸림)

A가 망토를 쓰고 정문으로 돌아온다 (1분걸림)

C,D가 망토를 쓰고 정문에서 기숙사로 간다 (10분걸림)

B가 망토를 쓰고 정문으로 돌아온다 (2분걸림)

A,B가 망토를 쓰고 정문에서 기숙사로 간다 (2분걸림)

따라서 총 17분이 걸리고 이것이 4사람이 정문에서 기숙사까지 들키지 않고 갈 수 있는 최소시간이다.

입력

학생들의 수 N (1 <= N <= 15)가 주어지고 한줄에 N개의 숫자들이 주어진다. 이 숫자는 각 학생이 정문에서 기숙사로 가는데 걸리는 시간을 의미한다.

출력

N명의 학생들이 정문에서 기숙사까지 가는데 걸리는 최소시간을 출력한다.

예제 입력

2 15 5

예제 출력

15

예제 입력

4 1 2 7 10

예제 출력

17

예제 입력

5 12 1 3 8 6

예제 출력

29
수학
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

11개의 풀이가 있습니다. 1 / 2 Page

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

링크 .

저는 여기에 서술한 알고리즘을 기반으로 코드를 짰어요. 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에 있는 체점 데이터는 모두 통과합니다.

+1 풀이는 답글로 작성해 주시면 좋겠습니다. 그리고 현재 HTML태그는 허용하고 있지만 가급적 마크다운으로 내용을 작성해 주시기 바랍니다. - 길가의풀, 2016/06/27 20:50 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Ruby

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

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

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

#=> puts safe_time["4 1 2 7 10"]
17
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

우선 가장 빠른 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로 했습니다. 일단 배열에 담아서 소팅을 먼저 시도를 하구요 서로서로 이동하기위해서 젤 빠른사람과 그다음번째로 빠른사람을 활용을 해야합니다. 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)

먼저 가장 빠른 두명을 보낸다음, 가장 빠른 한명이 돌아오고 이후 가장 느린 두명을 보냅니다. 두번째로 빠른 사람이 돌아오게 됩니다. 이런식으로 쭉 진행하다가 못 간 사람이 한명이 남거나 없게 되면 그 경우를 계산합니다. 아 진짜 코드 구리네요. 언제쯤 멋지게 작성할 수 있을까.. - Dr.Choi, 2016/07/05 00:05 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

실제 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;
}
1 3 이동 - 1 돌아옴 - 8 12 이동 - 3 돌아옴 - 1 6 이동 - 1 돌아옴 - 1 3 이동 / 3+1+12+3+6+1+3=29라서 29가 맞아요 - 한 성탁, 2016/08/30 11:10 M D
답변 감사합니다. 덕분에 코드 수정할 수 있었고 잘 이해못한 알고리즘도 이해하게 됐습니다~ - 코딩초보, 2016/08/30 15:27 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

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에서 작성하였습니다.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.

수학 x 4
연관 문제

언어별 풀이 현황
전 체 x 11
cpp x 3
ruby x 1
python x 5
기 타 x 1
java x 1