출처 : 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
```{.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이 되면 마무리 합니다.
2017年02月20日 22:40
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);
}
}
2017年04月02日 01:41
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;
}
}
풀이 작성