[SWEA] 2383. 점심 식사시간 - Simulation
제출일 : 2019-11-12
문제 풀이 시간 : 2D
난이도 : ★★★★★
Problem
link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu
Constraints
- 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는데, C/C++/Java 모두 3초
- 방의 한 변의 길이 N은 4 이상 10 이하의 정수이다. (4 ≤ N ≤ 10)
- 사람의 수는 1 이상 10 이하의 정수이다. (1 ≤ 사람의 수 ≤ 10)
- 계단의 입구는 반드시 2개이며, 서로 위치가 겹치지 않는다.
- 계단의 길이는 2 이상 10 이하의 정수이다. (2 ≤ 계단의 길이 ≤ 10)
- 초기에 입력으로 주어지는 사람의 위치와 계단 입구의 위치는 서로 겹치지 않는다.
input
입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 방의 한 변의 길이 N이 주어진다.
다음 N줄에는 N*N 크기의 지도의 정보가 주어진다.
지도에서 1은 사람을, 2 이상은 계단의 입구를 나타내며 그 값은 계단의 길이를 의미한다.
Output
테스트 케이스의 개수만큼 T줄에 T개의 테스트 케이스 각각에 대한 답을 출력한다.
각 줄은 "#x"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (x는 1부터 시작하는 테스트 케이스의 번호이다)
Example
input
10
5
0 1 1 0 0
0 0 1 0 3
0 1 0 1 0
0 0 0 0 0
1 0 5 0 0
5
0 0 1 1 0
0 0 1 0 2
0 0 0 1 0
0 1 0 0 0
1 0 5 0 0
…output
#1 9
#2 8
…Solution & Inpression
모의 SW 역량테스트문제
- 지도의 크기가 $N\times N$이고 사람, 계단의 길이가 주어진다.
- 사람은
1계단의 길이는2 이상 10 이하 - 계단의 개수는
2개이며 사람의 수는 최대10명이다
- 사람은
- 각 사람은 두 계단 중 한곳에 도착하여, 계단을 내려간다.
- 계단을 완전이 내려가는 시간은
계단의 길이 K만큼의 시간이 소요된다. - 계단은 최대 3명까지 동시에 이용이 가능
- 계단에 도착하면
1분 후에 용이 가능
- 계단을 완전이 내려가는 시간은
계단의 개수가 2개로 고정되기때문에 중복순열을 이용하여 각 사람이 이용할 수있는 모든 경우를 구한뒤
해당 경우의 시간을 구해 문제를 해결하였다.
지금까지 풀었던 문제중에 가장 어려웠던 문제였다.
Code
언어 : JAVA
메모리 : 36,012 kb
실행시간 : 177 ms
import java.io.FileInputStream;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
class Point { // 방에서의 위치를 나타내는 클래스
int r, c;
public Point(int r, int c) {
this.r = r;
this.c = c;
}
}
public class Solution {
static int N, M, S;
static int match[];
static Point[] man;
static Point[] stair;
static int[] length;
static int answer;
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("res/input.txt"));
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
N = sc.nextInt();
M = 0; // 사람 수
S = -1; // 계단 수
man = new Point[10]; // 최대 사람은 10명(위치 좌표를 저장)
stair = new Point[2]; // 계단은 2개(위치 좌표를 저장)
length = new int[2];// 계단의 길이 저장
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
int tmp = sc.nextInt();
if (tmp == 1)
man[M++] = new Point(i, j);
else if (tmp != 0) {
stair[++S] = new Point(i, j);
length[S] = tmp;
}
}
}
answer = Integer.MAX_VALUE;
match = new int[M];
dfs(0); // 모든 경우의 수를 구한다.
System.out.println("#" + tc + " " + answer);
}
sc.close();
}
// 중복순열: 모든 경우의 수를 구한다 최대 2^10
private static void dfs(int depth) {
if (depth == M) {
solve();
return;
}
for (int i = 0; i < 2; i++) {
match[depth] = i;
dfs(depth + 1);
}
}
// 각사람이 어느 계단을 이용할 지 정해졌을 때에 필요한 시간을 계산하는 함수
private static void solve() {
PriorityQueue<Integer> pq0 = new PriorityQueue<>();
PriorityQueue<Integer> pq1 = new PriorityQueue<>();
for (int i = 0; i < M; i++) {
if (match[i] == 0)
pq0.add(dist(man[i], stair[0]));
else
pq1.add(dist(man[i], stair[1]));
}
int man = M; // 남은 이용자.
int[] stair0 = new int[3]; // 계단을 이용하는 사람들의 남은 이용시간.
int[] stair1 = new int[3];
int time = 0;
while (true) {
// 종료 조건 : 계단을 모든 이용자가 이용할 때 까지.
if (man == 0) {
boolean flag = true;
for (int i = 0; i < 3; i++) {
if (stair0[i] != 0) {
flag = false;
break;
}
if (stair1[i] != 0) {
flag = false;
break;
}
}
if (flag)
break;
}
for (int i = 0; i < 3; i++) { // 계단은 최대 3명까지 동시에 이용할 수 있다.
if (stair0[i] == 0) { // 현재 이용하는 사람이 없을때
if (!pq0.isEmpty()) { // 이용할 사람이 있고(큐가 비어있지 않다면)
if (pq0.peek() <= time) { // 도착했다면
man--; // 남은 이용자수를 내린다.
stair0[i] = length[0];// 해당 계단의 이동시간을 주고
pq0.poll();
}
}
} else { // 현재 계단을 사용하고 있다면
stair0[i]--; // 값을 내리고
if (stair0[i] == 0) {// 계단을 이용하고 있지 않다면.
if (!pq0.isEmpty()) {
if (pq0.peek() <= time) {
man--; // 이용자를 내린다.
stair0[i] = length[0];
pq0.poll();
}
}
}
}
if (stair1[i] == 0) { // 현재 이용하는 사람이 없을때
if (!pq1.isEmpty()) { // 이용할 사람이 있고(큐가 비어있지 않다면)
if (pq1.peek() <= time) { // 도착했다면
man--; // 남은 이용자수를 내린다.
stair1[i] = length[1];// 해당 계단의 이동시간을 주고
pq1.poll();
}
}
} else { // 현재 계단을 사용하고 있다면
stair1[i]--; // 값을 내리고
if (stair1[i] == 0) {// 계단을 이용하고 있지 않다면.
if (!pq1.isEmpty()) {
if (pq1.peek() <= time) {
man--; // 이용자를 내린다.
stair1[i] = length[1];
pq1.poll();
}
}
}
}
} // end of for
time++;
} // end of while
if (time < answer)
answer = time;
}
private static int dist(Point man, Point stair) {
return Math.abs(man.r - stair.r) + Math.abs(man.c - stair.c);
}
}'Problem > SWEA' 카테고리의 다른 글
| [SWEA] 4613. 러시아 국기 같은 깃발 D4 - 조합 (0) | 2019.11.17 |
|---|---|
| [SWEA] 4615. 재미있는 오셀로 게임 D3 - Simulation (0) | 2019.11.16 |
| [SWEA] 2117. 홈 방범 서비스 - Simulation (0) | 2019.11.12 |
| [SWEA] 5658. 보물상자 비밀번호 - Simulation (0) | 2019.11.03 |
| [SWEA] 6109. 추억의 2048게임 D4 - Simulation (0) | 2019.11.03 |
