출처 : 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
이 문제에 관한 흥미로운 페이퍼가 있습니다
링크 .
저는 여기에 서술한 알고리즘을 기반으로 코드를 짰어요. 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에 있는 체점 데이터는 모두 통과합니다.
2016年06月08日 23:06
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));
}
2016年07月03日 18:40
실제 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;
}
풀이 작성