[ SWEA ] 2383. [모의 SW 역량테스트] 점심 식사시간 - JAVA

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl

SW Expert Academy

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다. : 문제 설명은 생략 한다...

시뮬 중에 어려운거 오랫만에 풀어 보는 기분이었다.. 흑흑 머리를 도르륵 도르륵 얼마나 굴리며, 종이도 써가면서 풀었는지..

[ 풀이 코드 ] 

package newProject;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class 점심식사시간 {
	static int P,S;
	static int ans;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb =new StringBuilder();
		for(int tc = 1; tc<=T; tc++) {
			int N = Integer.parseInt(br.readLine());
			ArrayList<Integer> PR= new ArrayList<Integer>();
			ArrayList<Integer> PC= new ArrayList<Integer>();
			ArrayList<Integer> SR= new ArrayList<Integer>();
			ArrayList<Integer> SC= new ArrayList<Integer>();	
			ArrayList<Integer> SL = new ArrayList<Integer>();
			int[][] arr =new int[N][N];
			for(int i =0; i< N ; i++) {
				StringTokenizer st =new StringTokenizer(br.readLine());
				for(int j =0; j<N ;j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
					switch(arr[i][j]) {
					case 0:
						break;
					case 1:
						PC.add(i);
						PR.add(j);
						break;
					default : 
						SC.add(i);
						SR.add(j);
						SL.add(arr[i][j]);
					}
				}
			}// 입력 완료 
			P = PC.size();// 사람수 
			S = SC.size(); // 계단 수 
			ans = Integer.MAX_VALUE;
			check(new int[P],0,PC,PR,SC,SR,SL);
			sb.append('#').append(tc).append(' ').append(ans).append('\n');
			
		}
		
		System.out.println(sb);
	}
	private static void check(int[] tmp, int p, ArrayList<Integer> PC, ArrayList<Integer> PR, ArrayList<Integer> SC,
			ArrayList<Integer> SR, ArrayList<Integer> SL) {
		if(p==P) {
			int time =0; 
			for(int s =0; s<S;s++) { 
				//tmp = new int[] {0,0,0,0,1,1};
				ArrayList<Integer> or = new ArrayList<Integer>();
				for(int i =0; i< P; i++) {
					if(tmp[i]==s) {
						//System.out.println("|"+ PR.get(i)+"-" + SR.get(s)+"| + | "+PC.get(i)+"-"+SC.get(s)+"|");
						or.add(Math.abs(PR.get(i)-SR.get(s))+ Math.abs(PC.get(i)-SC.get(s)));
					}
				}
				Collections.sort(or);
				int t =0; // 처음 사람이 도착 한 시간
				int out = SL.get(s);// 계단 길이 
				int size = or.size();
				for( int i = 3; i<size; i++) {
					if(or.get(i)-or.get(i-3)<out) {
						or.set(i, out+or.get(i-3));
					}
				}
				time = (size>0 && or.get(size-1)+out+1>time)?or.get(size-1)+out+1:time;
				//System.out.println(time);
			}
			ans = time<ans?time:ans;
			return;
		}
		for(int i =0; i< S;i++) {
			tmp[p] = i;
			check(tmp, p+1, PC,PR,SC,SR,SL);
		}
		
	}
}

[풀이 ]

이 문제는 시뮬레이션인데, 이런 시뮬이 다있나 하는 정도의 시뮬...

우선 시간 계산에 대한 이해가 아주 애매하다.. 어려워서 그냥 예시로 있는 경우의 수를 보고 그대로 되나 확인해 나갔다.. 이거 진짜 에디터 없었으면 절대 못푼다 수준...

어떻게 풀어야할지 막막해서 밑에 있는 댓글을 유심히 봤다. 

이 댓글에서 해결책을 찾아서 겨우 풀기 시작했다. 

이 문제는 중복 조합을 만들고, 시뮬레이션을 돌리는 간단한 문제 같지만 그냥 문제 이해가 어려운 걸로.. 

사실 생각은 간단하다. 중복 조합을 만들고, 시뮬을 돌린다..

[코드 설명 ] 

 

먼저 문제를 풀기 전에, P 사람 수 , S 계단 수는 전역 변수로 선언 해 주었다. 그리고 중복 조합을 만들면서 최소값을 찾아야 하니 ans도..

이 부분은 모두가 쉽게 알 수 있는 입력 부인데, 사람위치를 PR,PC에 넣어주고, 계단 위치를 SR,SC로 넣어주었다.  

문제 설명에

이렇게 쓰여 있어서 그대로 따라했다. 

그리고 전역 변수를 초기화 해주고, 

중복조합을 만들 check함수를 부르게 된다. 

parameter는 사람이 어떤 계단에 들어갈지 적어둘 tmp, 사람 순서대로 중복조합을 만드니 사람 번호 p, 그리고 입력부에서 받았던, PR,PC,SC,SR 그리고 계단의 길이 Stair Length 인 SL 까지를 파라미터로 가진다. 

처음에는 이렇게 return 포인트인 if(p ==P)를 만들어주고, 중복 조합을 돌 수 있도록, 함수를 만들어 준다. 

그렇다면 사람이 6명, 계단이 2개가 있다면, [0,0,0,0,0,0], [0,0,0,0,0,1],[0,0,0,0,1,0] ....[1,1,1,1,1,0], [1,1,1,1,1,1]까지의 배열이 생성되며 반복문을 돌게 된다. 

p가 총 사람수가 되는 점에 다다르면 이제 시뮬레이션이 시작되는데,

몇 번째 계단인지 반복하며 같은 계단에 들어갈 사람을 구해준다. 예를 들어 첫번째 계단에 들어갈 사람이 처음 s=0일때 or ArrayList에 저장된다. 

몇번쨰 사람인지는 중요하지 않고 중요한건 몇분때 계단 앞으로 오는지 이므로 

| PR - SR ] + | PC - SC |를 계산하여 or에 담아준다. 

그리고 도착한 시간 별로 오름차순으로 정렬한다. 그러면 2,3,3,.. 이런 식으로 배열이 정렬된다. 

그리고 중요한 값인 나갈때 걸리는 시간인 out 즉, 계단 길이를 따로 저장해 주고, 반복문을 돌리며 맨 마지막 시간까지를 구할 것이므로 or의 길이인 size도 따로 저장해 둔다. 

그렇게 이 부분이 메인이 되는데, 

3명만 계단에 들어갈 수 있으므로, 3명 전의 사람이 아직 계단을 빠져나가지 못했으면, 계단을 빠져 나갈 시간까지 값이 그 사람이 계단에 들어가는 시간이 되므로 

현재 i번째 들어오는 사람의 계단 입장 시간을 out+or.get(i-3)으로 바꿔준다.

예를 들어 or = [2,2,3,4,4,7] 이라면 

i=3일 때는  out이 3이라면, 

[2,2,3,5, 4,7]이 되고, 

i=4이면 [2,2,5,5,7] , i=5일때는 [2,2,5,5,7]이 유지된다. 

그렇다면 이제 마지막 값인 7이 마지막 사람이 계단에 입장하는 시간이 되고, 

time에 or.get(size-1) + out + 1을 넣어주면 된다. 

다 완전히 빠져나온 시간이므로 1을 더하게 된다. 

모든 계단을 다 통과하는 시간 중 가장 긴 값이 time이 되므로 , or.get(size-1)+out + 1 이 저장된 time보다 클 경우 

time은 갱신 되게 된다. 

 

이러한 과정을 반복하면서 

가장 짧은 시간인 ans를 찾아내고, 리턴하면, 

다시 main함수의 안으로 들어와서 

값을 tc별로 저장하고, 마지막에 출력해 주면 된다. 

 

진짜 종이 없었으면 못풀뻔 해따.. 괜히 삼성 역테 볼때 종이를 주는게 아니구나...