관리 메뉴

KoreanFoodie's Study

SW 역량테스트 - [모의 SW 역량테스트] 점심 식사시간 문제 풀이/해답/코드 (C++ / JAVA) 본문

Data Structures, Algorithm/SW 역량테스트

SW 역량테스트 - [모의 SW 역량테스트] 점심 식사시간 문제 풀이/해답/코드 (C++ / JAVA)

hashnut 2020. 9. 29. 11:39


SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다!

해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 

코드에 대한 설명은 주석을 참고해 주세요 :)

 


문제 링크 : swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl&

해답 코드 : 

 

// c++

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

vector<pair<int, int>> people;
vector<pair<int, int>> stair;

int N;
int board[10][10] = { 0, };

int mappingTable[10];
int answer;
int peopleCnt;

int getTime() {
	int t = 0;
	int chk = 0;
	int d[10];
	queue<int> c[2];

	for (int i = 0; i < peopleCnt; i++) {
		d[i] = abs(people[i].first - stair[mappingTable[i]].first) + abs(people[i].second - stair[mappingTable[i]].second);
	}

	while (true) {
		if (t >= answer) return t;

		if (chk == peopleCnt) return t;

		//계단에 들어간 경우
		for (int i = 0; i < 2; i++) {
			int cs = c[i].size();
			for (int j = 0; j < cs; j++) {
				int top = c[i].front();
				c[i].pop();
				top--;
				if (top != 0)
					c[i].push(top);
				else {
					chk++;
				}
			}
		}

		// 입구에 도착한 경우
		for (int i = 0; i < peopleCnt; i++) {
			if (t == d[i]) {
				if (c[mappingTable[i]].size()<3)//계단 입구 도착시 사람이 아무도 없다면
					c[mappingTable[i]].push(board[stair[mappingTable[i]].first][stair[mappingTable[i]].second]);
				else {
					c[mappingTable[i]].push(board[stair[mappingTable[i]].first][stair[mappingTable[i]].second] + c[mappingTable[i]].front());
				}
			}
		}
		t++; // 시간 증가

	}

}

void recursive(int cnt) {

	// 종료부
	if (cnt == people.size()) {
		int tmp = getTime();
		if (answer > tmp) answer = tmp;
		return;
	}

	// 분할부
	mappingTable[cnt] = 0; recursive(cnt + 1);
	mappingTable[cnt] = 1; recursive(cnt + 1);

}

int main() {

	int T;
	cin >> T;

	for (int test_case = 1; test_case <= T; test_case++) {
		cin >> N;
		people.clear();
		stair.clear();
		for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
			cin >> board[i][j];
			if (board[i][j] == 1) people.push_back({ i,j });
			else if (board[i][j] > 1) stair.push_back({ i,j });
		}
		peopleCnt = people.size();
		answer = 99999999;
		recursive(0);
		cout << "#" << test_case << ' ' << answer << '\n';

	}
	return 0;

 

Version 2
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

vector<pair<int, int>> people;
vector<pair<int, int>> stair;

int N;
int board[10][10] = { 0, };

int mappingTable[10];
int answer;
int peopleCnt;

int getTime() {
	int t = 0;
	int chk = 0;
	int d[10];
	queue<int> c[2];

	for (int i = 0; i < peopleCnt; i++) {
		d[i] = abs(people[i].first - stair[mappingTable[i]].first) + abs(people[i].second - stair[mappingTable[i]].second);
	}

	while (true) {
		if (t >= answer) return t;

		if (chk == peopleCnt) return t;

		//계단에 들어간 경우
		for (int i = 0; i < 2; i++) {
			int cs = c[i].size();
			for (int j = 0; j < cs; j++) {
				int top = c[i].front();
				c[i].pop();
				top--;
				if (top != 0)
					c[i].push(top);
				else {
					chk++;
				}
			}
		}

		// 입구에 도착한 경우
		for (int i = 0; i < peopleCnt; i++) {
			if (t == d[i]) {
				if (c[mappingTable[i]].size()<3)//계단 입구 도착시 사람이 아무도 없다면
					c[mappingTable[i]].push(board[stair[mappingTable[i]].first][stair[mappingTable[i]].second]);
				else {
					c[mappingTable[i]].push(board[stair[mappingTable[i]].first][stair[mappingTable[i]].second] + c[mappingTable[i]].front());
				}
			}
		}
		t++; // 시간 증가

	}

}

void recursive(int cnt) {

	// 종료부
	if (cnt == people.size()) {
		int tmp = getTime();
		if (answer > tmp) answer = tmp;
		return;
	}

	// 분할부
	mappingTable[cnt] = 0; recursive(cnt + 1);
	mappingTable[cnt] = 1; recursive(cnt + 1);

}

int main() {

	int T;
	cin >> T;

	for (int test_case = 1; test_case <= T; test_case++) {
		cin >> N;
		people.clear();
		stair.clear();
		for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
			cin >> board[i][j];
			if (board[i][j] == 1) people.push_back({ i,j });
			else if (board[i][j] > 1) stair.push_back({ i,j });
		}
		peopleCnt = people.size();
		answer = 99999999;
		recursive(0);
		cout << "#" << test_case << ' ' << answer << '\n';

	}
	return 0;

 

SW 역량테스트 준비 - [모의 SW 역량테스트] 풀이 / 코드 / 답안 (C++ / JAVA)

SW 역량테스트 준비 - C++ 코드, Java 코드

SW 역량테스트 준비 - 백준 알고리즘 문제

0 Comments
댓글쓰기 폼