[2383] 점심 식사시간

풀이

1. SWEA의 해설을 보면서 풀이를 정리했다.
2. 두 개의 계단에 대해서 독립적으로 코드를 작성하면서 코드 길이르 줄이고, 에러도 줄인다.
3. 각 사람에 대해서 몇 초에 계단을 다 내려갈 수 있는지를 구하는 코드를 여러번 쓰면서 코드를 줄인다.
4. 자세한 풀이는 [모의 SW 역량테스트 해설]포스팅에 정리하였다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
using namespace std;
struct PT {
	int r, c;
	PT() {}
	PT(int _r, int _c) : r(_r), c(_c) {}
}people[10], stair[2];

int map[10][10];
int match[11] = { 0, }; //match[x]=y : x번째 사람이 이용할 계단은 y
int ans = 0;
int dist(int pidx, int sidx) {//person_idx, stair_idx
	int dr = abs(people[pidx].r - stair[sidx].r);
	int dc = abs(people[pidx].c - stair[sidx].c);
	return dr + dc;
}

int update(int M) {
	//각 사람이 이용할 계단이 정해져있는 상태, 두 개의 계단을 독립적으로 판단
	int one_state_end = 0;
	for (int sidx = 0; sidx < 2; sidx++) {//stair_idx
		int arrive[20] = { 0, }; //arrive[x] = y : x분에 계단에 도착하는 사람의 수 y
		int on[35] = { 0, }; //on[x] = y : x분에 계단에 타고 있는 사람의 수 y
		for (int i = 0; i < M; i++) {
			if (match[i] == sidx) { //sidx 계단을 이용하고 있는 사람을 찾기
				arrive[dist(i, sidx)]++;//이 사람이 몇 초에 sidx 계단에 도착하는지 계산해서 count
			}
		}
		int one_person_end = 0;
		for (int t = 1; t <= 20; t++) {// t초 일 때의 상황
			//t초에 도착하는 사람이 있으면 이들을 모두 계단에 내려보내면서 각자가 끝나는 시간을 갱신
			int ct = t + 1; //도착한 후 1분 뒤부터 내려간다
			while (arrive[t] > 0) {//x분에 계단을 내려가기 시작하는 사람 중 한 명씩 한 명씩 내려감
				arrive[t] -= 1;
				int slen = map[stair[sidx].r][stair[sidx].c]; //계단의 길이 
				while (slen > 0) {//계단의 길이만큼
					//계단에 있는 사람이 3명이하이면 
					if (on[ct] < 3) {
						on[ct] += 1;
						slen -= 1;
						if (slen == 0) {//계단을 모두 내려가면 그 사람이 도착한 시간을 갱신
							one_person_end = max(one_person_end, ct+1); //slen만큼 내려가서 1분 뒤에!!!!! 완료
							ct = t + 1; //초기화!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
							break;
						}
					}
					ct += 1;
				}
			}
		}
		one_state_end = max(one_state_end, one_person_end);
	}
	return one_state_end;
}

void dfs(int x, int M) {
	if (x == M) {
		int tans = update(M);
		ans = min(ans, tans);
		return;
	}
	for (int sidx = 0; sidx < 2; sidx++) { //stair_idx
		match[x] = sidx;
		dfs(x + 1, M);
	}
}

int main(void) {
	int tcase = 0; scanf("%d", &tcase);
	for (int tc = 1; tc <= tcase; tc++) {
		ans = 0xFFFFFF;
		int n = 0; scanf("%d", &n);
		int M = 0, S = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				scanf("%d", &map[i][j]);
				if (map[i][j] == 1) people[M++] = PT(i, j);
				else if (map[i][j] >= 2) stair[S++] = PT(i, j);
			}
		}
		dfs(0, M);
		printf("#%d %d\n", tc, ans);
	}

	return 0;
}

처음에 3시간 넘게짜고 기본 TC도 통과 못한 코드

#define  _CRT_SECURE_NO_WARNINGS
/*
2019-00-00
장환석

*/
#include <cstdio>
#include <vector>
#include <algorithm>
#include <deque>
using namespace std;

typedef struct person{
	int r;
	int c;
	int onstair;
	int dst_a; //계단 a까지와의 거리
	int dst_b; //계단 b까지와의 거리
	person() {
		r = -1;
		c = -1;
		onstair = -1;
		dst_a = -1;
		dst_b = -1;
	}
	person(int _r, int _c, int _onstair, int _dst_a, int _dst_b) {
		r = _r;
		c = _c;
		onstair = _onstair;
		dst_a = _dst_a;
		dst_b = _dst_b;
	}
	
};

typedef struct stair {
	int r;
	int c;
	int len;
	stair() {
		r = -1;
		c = -1;
		len = -1;
	}
	stair(int _r, int _c, int _len) {
		r = _r;
		c = _c;
		len = _len;
	}

};

int map[10][10];
vector<person> people;
stair sa, sb;
vector<person> wait_a, wait_b; //계단 a와 b를 기다리고 있는 사람들
deque<person> on_a, on_b;//계단 a와 b에 타고 있는 사람들

bool compareA(person a, person b) {
	if (a.dst_a != b.dst_a) return a.dst_a < b.dst_a;
	else return a.r < b.r;
}

bool compareB(person a, person b) {
	if (a.dst_b != b.dst_b) return a.dst_b < b.dst_b;
	else return a.r < b.r;
}


int goDown(void) {
	//여기에서 wait_a를 sort해버려서 문제가 발생했었다. 
	vector<person> wa, wb; //계단 a와 b를 기다리고 있는 사람들
	printf("===A===\n");
	for (int i = 0; i < wait_a.size(); i++) {
		wa.push_back(wait_a[i]);
		printf("%d, %d\n", wa[i].r, wa[i].c);
	}
	printf("===B===\n");
	for (int i = 0; i < wait_b.size(); i++) {
		wb.push_back(wait_b[i]);
		printf("%d, %d\n", wb[i].r, wb[i].c);
	}
	//wait_a 계단 거리별로 sort
	sort(wa.begin(), wa.end(), compareA);
	//wait_b 계단 거리별로 sort
	sort(wb.begin(), wb.end(), compareB);
	//계단 내려 보내기 진행
	int curr_t = 0;
	vector<person>::iterator it_a, it_b;
	it_a = wa.begin();
	it_b = wb.begin();
	//마지막 사람까지 다 탔고, 타고 있는 사람 없으면
	while (true) {
		curr_t += 1;
		printf("============curr_t %d초 째에=========\n", curr_t);
		while (!on_a.empty() && (on_a[0].onstair == sa.len )) {
			printf("A 내리게 하기\n");
			on_a.pop_front();
		}
		while (!on_b.empty() && (on_b[0].onstair == sb.len )) {
			printf("B 내리게 하기\n");
			on_b.pop_front();
		}
		//wait_a에 사람이 있고, on_a에 더 태울 수 있고, 다음에 탈 사람이 도착한 상태이면
		while (it_a != wa.end() &&  on_a.size() < 3 && (*it_a).dst_a <= curr_t) {
			printf("A에 사람 태우고\n");
			on_a.push_back(*it_a);
			++it_a;
		}
		while (it_b != wb.end() && on_b.size() < 3 && (*it_b).dst_b <= curr_t) {
			printf("B에 사람 태우고\n");
			on_b.push_back(*it_b);
			++it_b;
		}
		//계단 내려가게 하고 다 내려가면 내리게 하기 //첫 째사람이 항상 가장 많이 계단을 내려갔을 것이다.
		for (int i = 0; i < on_a.size(); i++) {
			printf("A 계단에서 내려가게 하기\n");
			on_a[i].onstair += 1;
		}
		
		for (int i = 0; i < on_b.size(); i++) {
			printf("B 계단에서 내려가게 하기\n");
			on_b[i].onstair += 1;
		}
		
		if (it_a == wa.end() && it_b == wb.end() && on_a.empty() && on_b.empty()) {
			break;
		}
	}
	printf("REUTNR %d\n\n", curr_t);
	return curr_t;
}


void setStair(int x, int len, int &ans) {
	if (x == len) {
		//각 계단에 할당된 사람들을 내려보내기
		 int tans = goDown();
		 ans = ans > tans ? tans : ans;
		 return;
	}
	//x번째 사람이 계단 a를 사용하는 경우
	wait_a.push_back(people[x]);
	setStair(x + 1, len, ans);
	wait_a.pop_back();
	//x번째 사람이 계단 b를 사용하는 경우
	wait_b.push_back(people[x]);
	setStair(x + 1, len, ans);
	wait_b.pop_back();
}

int main(void) {
	int tcase = 0; scanf("%d", &tcase);
	for (int tc = 1; tc <= tcase; tc++) {
		people.clear();
		sa = { -1,-1, -1 };
		sb = { -1,-1, -1 };
		wait_a.clear();
		wait_b.clear();
		on_a.clear();
		on_b.clear();
		int ans = 0xFFFFFFF, n = 0; scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				scanf("%d", &map[i][j]);
				if (map[i][j] == 1) {
					people.push_back(person(i,j,-1,-1,-1));
					//printf("%d, %d 위치에 있는 사람 push\n", i, j);
				}
				else if (map[i][j] >= 2) {
					if (sa.r == -1) {
						sa.r = i;
						sa.c = j;
						sa.len = map[i][j];
						//printf("%d, %d, %d 위치에 있는 계단 세팅\n",sa.r, sa.c, sa.len);
					}
					else {
						sb.r = i;
						sb.c = j;
						sb.len = map[i][j];
						//printf("%d, %d, %d 위치에 있는 계단 세팅\n", sb.r, sb.c, sb.len);
					}
				}
			}
		}
		for (int i = 0; i < people.size(); i++) {
			people[i].dst_a = abs(people[i].r - sa.r) + abs(people[i].c - sa.c);
			people[i].dst_b = abs(people[i].r - sb.r) + abs(people[i].c - sb.c);
		}
		setStair(0, people.size(), ans);
		printf("#%d %d\n", tc, ans);
	}
	return 0;
}