출처 : 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
답변 감사합니다.
덕분에 코드 수정할 수 있었고 잘 이해못한 알고리즘도 이해하게 됐습니다~
#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;
}
2016年08月29日 17:13
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 처음 써봤는데 배열과는 다른 매력이 있네요.
2018年01月26日 15:32
풀이 작성