점심 식사 시간

이 문제의 핵심은, 계단에 3명이 다 차있을 경우 처리하는 부분이다. 계단s의 길이를 K라고 한다면, 먼저 s를 선택한 사람들이 s에 도착한 시간을 저장한다, 오름차순 정렬. 3명 이하인 경우, 마지막 요소의 값 +K+1 한 값이 전체 사람들이 이동완료하는 데 걸린 시간이 된다.

3명을 초과하는 경우, s에 도착한 시간을 저장하는 컬렉션을 arrivalTime이라고 하자. i=0,1,2 까지 3명의 사람은 s에 도착한 시간을 저장한다. 즉, 계단에 진입하기 1분 전 시간을 저장한다. 마찬가지로, i(i>=3)번째 사람은 i-3번째 사람도 계단에 진입하기 1분 전 시간을 저장하도록한다. arrivalTime.get(i) : i번째 사람이 s에 도착한 시간 arrivalTime.get(i-3) : i-3번째 사람이 s에 도착한 시간. i-3이 K+1이 지나면 이동을 완전히 완료하여 i가 계단에 진입할 수 있다. 여기서 이 솔루션에서는 진입하기 1분전 시간을 저장할 것이기 때문에, arrivalTime.get(i)를 i번째 사람이 계단에 진입하기 1분전 시간으로 arrivalTime.get(i-3) +K 로 갱신해준다!

• BFS

• 트럭 문제

• 순열 문제

• (2021 카카오 블라인드)카드 짝맞추기

내 접근 방법 - 2021 카카오 블라인드 카드 짝맞추기 2가지 경우의 수가 존재할 때, 각각의 최솟값을 선택하여 전체 모든 경우의 수를 구하는 문제 솔루션 뼈대로 접근했다. 계단까지 이동하는 거리는 구했는데 이후 순열 생성하는 재귀함수 호출 부분에서 로직을 제대로 완성해내지 못했다.

처음엔 위 후보들 중에 BFS 문제 유형이라고 생각했지만 문제를 계속 생각해보면, 단순히 계단까지의 최단거리를 구해서 최단거리의 계단을 선택하는 것이 최소 시간을 보장할 수 없다는 것을 알 수 있다.

그렇기 때문에 입력 크기에 따라서, 모든 경우를 다 해보는 방법을 생각해볼 수 있다. 사람10 명마다 2개의 계단을 선택하는 경우의 수가 있기 때문에 총 경우의 수는 2^10이고, 1024는 1억보다 매우 작기 때문에 모든 경우의 수를 다 해볼 수 있다.

각 사람마다 계단을 선택하는 재귀함수를 구현하는 것까지는 성공했다. 그런데 go(int index,int time) 으로 스펙을 잡았는데, index번째 사람의 계단을 선택하는 부분은 그렇다고 치지만ㄴ, time이라는 부분에서, 현재까지 index사람이 계단 선택하기 까지 걸린 시간을 구해서 다음 재귀함수에 넣어준다는 것은 어딘가 어색했다. 왜냐하면 시간의 흐름에 따라 계단에 들어간 사람들을 이동시켜야 하고, index번째 사람 하나하나를 계단 선택한다고 해도, index+1번째 사람에서 의미가 있을까? 시간 개념을 적용하지 못한 것 같다는 생각이 들었다.

제대로 구현하지 못한 부분

1. 계단 이동, 이동완료

2. 계단에 3명이 있은 경우(웨이팅이 있는 경우) 처리

정답 솔루션 핵심

내가 생각했던 순열 선택 관점의 접근 방법이 어느 정도 맞은 것 같다. 다만, 순서가 상관없기 때문에 순열이 아니라 조합으로 가야한다. 몇번째 사람이 선택했는지는 중요하지 않고, 시간이 몇 분에 계단 입구에 도착했는지, 시간 값이 중요하다.

구해야하는 것은 다음과 같다. ① 선택한 계단까지의 거리 ② 계단에 도착한 후! 이동을 완료하는 데 걸리는 시간(3명이 다 차있을 경우 처리⭐️)

알고리즘 핵심 P명의 사람들 순열관점에서 계단 선택 : 재귀함수로 구현, P명 계단을 모두 선택한 경우, 본격적으로 시뮬레이션이 시작된다! ⭐️⭐️⭐️⭐️⭐️

1. 전체 사람들이 이동 완료하는 데에 걸린 시간 time = 0;

2. 각 계단에 대해 반복문을 반복한다.

3. 현재 계단 s를 선택한 사람이 ① 계단까지 이동하는 데 걸린 시간을 컬렉션에 저장한다 : 각 사람들에 대해 반복문으로 반복한다.

4. ①계단까지 이동하는 데 걸린 시간을 저장한 컬렉션 오름차순으로 정렬한다.

5. 오름차순 정렬한 후, 사람이 3명 이하일 경우, 마지막 요소에 대해 K+1+or.get(or.size()-1) 한 값이 전체 이동 완료하는 데 걸리는 시간이 된다.

6. 오름차순 정렬한 후, 사람이 3명 초과한 경우⭐️⭐️ 현재 i번째 사람부터 3명을 초과했다고 하자. 이 사람은 i-3번째 사람이 계단 내려가는 것을 완료한 후에 계단에 진입할 수 있다. i번째 사람이 계단에 도착한 시간 : or.get(i) i-3번째 사람이 계단에 도착한 시간 : or.get(i-3) i-3번째 사람이 계단 내려가는 것을 완료한 시간 : K+or.get(i-3)+1이기 때문에 i번째 사람이 계단 진입할 수 있는 시간은 K+or.get(i-3)+1 아닌가? i의 계단입장시간은 왜 K+or.get(i-3)+1이 아니라 K+or.get(3)이 될까?

7. 현재 계단s에서 선택한 인구수가 양수이면, 마지막요소의 or컬렉션 값+K+1 과 비교하여 더 큰 값으로 time을 갱신시킨다.

8. ans는 time의 최솟값으로 갱신

9. 다음 경우 호출하는 부분 : P 크기의 배열 생성 후, 각 사람이 선택하는 계단 번호를 저장하고, 재귀함수 호출&실행한다.

2번째 풀었을 때 틀린 이유 - 스코프 문제

1. 각각의 경우 이동하는 데 걸린 총 시간 time 변수 모든 사람의 계단을 다 선택하고 난 후, 각각의 경우에 대해 걸린 시간 time을 구한다. time = 계단1 이동시간 + 계단2 이동시간이기 때문에 계단 반복문 이전에 위치해야한다.

2. time 변수들의 최솟값을 저장하는 최종 해 ans 변 그리고 time 값들 중 최솟값을 취하는 최종해 ans는 각각의 경우, 계단1과 계단2 이동시간을 다 구하고 난 후의 time에 대해 최솟값을 취하는 것이기 때문에 계단 반복문 밖에 위치해야한다!

이전 코드: time과 ans 변수 모두 계단 반복문 내에 있기 때문에 오답이 출력된다. time 변수의 정의를 제대로 모르기 때문이였다. 계단1 이동시간 + 계단2 이동시간 모두 합산한 개념인데 각 계단 별로 최솟값을 구하는 걸로 착각했다.

static void solve(int index) {//solve는 index번째 사람이 계단 이동하는데 걸린 시간을 더해간다? 아님. 이상함. 시간의 차원이 필요하다.
		//재귀를 종료할 때 : 모든 선택한 경우, 시뮬레이션!
		if(index == pCnt) {
			for(int s=0;s<sCnt;s++) {
				int time=0;//각 경우의 수마다 전체 사람 이동 완료 시간 저장
				LinkedList<Integer> aT = new LinkedList<>();
				for(int p=0;p<pCnt;p++) {
					if(Selected[p] == s) {
						aT.add(Math.abs(People[p].x-Stairs[s].x)+Math.abs(People[p].y-Stairs[s].y));
					}
				}
				Collections.sort(aT);
				//3명 초과인 경우 처리
				int size = aT.size();
				int K = Stairs[s].K;
				for(int i=3;i<size;i++) {
					if(aT.get(i)-aT.get(i-3)<K) {
						aT.set(i, aT.get(i-3)+K);
					}
				}
				//부분해 time 값 갱신 : 현재 계단 s 아무도 선택안하는 경우도 있기 때문에 aT가 양수인 경우만 처리!
				time = (size>0 && aT.get(size-1)+K+1 > time)? aT.get(size-1)+K+1:time;
				ans = ans>time?time:ans;//최종해 ans 최솟값 갱신 :모든 경우에 대해 모든 time들 중 최솟값을 갱신하기 때문에 계단 반복문 밖에 위치해야함!
			}//s-for문
			return;
		}
		//index번째 사람 계단 선택 후 재귀호출
		for(int s=0;s<sCnt;s++) {
			Selected[index] = s;
			solve(index+1);
		}
	}

static void solve(int index) {//solve는 index번째 사람이 계단 이동하는데 걸린 시간을 더해간다? 아님. 이상함. 시간의 차원이 필요하다.
		//재귀를 종료할 때 : 모든 선택한 경우, 시뮬레이션!
		if(index == pCnt) {
		  int time=0;//각 경우의 수마다 전체 사람 이동 완료 시간 저장
			for(int s=0;s<sCnt;s++) {
				LinkedList<Integer> aT = new LinkedList<>();
				for(int p=0;p<pCnt;p++) {
					if(Selected[p] == s) {
						aT.add(Math.abs(People[p].x-Stairs[s].x)+Math.abs(People[p].y-Stairs[s].y));
					}
				}
				Collections.sort(aT);
				//3명 초과인 경우 처리
				int size = aT.size();
				int K = Stairs[s].K;
				for(int i=3;i<size;i++) {
					if(aT.get(i)-aT.get(i-3)<K) {
						aT.set(i, aT.get(i-3)+K);
					}
				}
				//부분해 time 값 갱신 : 현재 계단 s 아무도 선택안하는 경우도 있기 때문에 aT가 양수인 경우만 처리!
				time = (size>0 && aT.get(size-1)+K+1 > time)? aT.get(size-1)+K+1:time;
			}//s-for문
			ans = ans>time?time:ans;//최종해 ans 최솟값 갱신 :모든 경우에 대해 모든 time들 중 최솟값을 갱신하기 때문에 계단 반복문 밖에 위치해야함!
			return;
		}
		//index번째 사람 계단 선택 후 재귀호출
		for(int s=0;s<sCnt;s++) {
			Selected[index] = s;
			solve(index+1);
		}
	}