삼성 SW 기출 문제 (3)

본 포스팅에서는 [스타트와 링크, 마법사 상어와 블리자드, 마법사 상어와 복제, 주사위 굴리기 2]를 다룹니다.

14889. (스타트와 링크) 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. 축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다.

#include<iostream>
#include<vector>
using namespace std;
int N;
int S[21][21];
vector<int> v;
int totalSum;
int minDiff = -1;
void makeTeam(int idx, int result) {
	if (v.size() == N / 2) {
		int temp = totalSum;
		for (int i = 0; i < v.size(); i++)
		{
			for (int j = 0; j < N; j++)
			{
				temp -= S[v[i]][j];
				temp -= S[j][v[i]];
			}
		}
		temp += result;
		int Diff = abs(result - temp);
		if (minDiff == -1) {
			minDiff = Diff;
			return;
		}
		if (Diff < minDiff) {
			minDiff = Diff;
		}
		return;
	}
	for (int i = idx; i < N; i++)
	{
		// 앞서 저장
		for (int j = 0; j < v.size(); j++)
		{
			result += S[j][i];
			result += S[i][j];
		}
		v.push_back(i);
		makeTeam(i + 1, result);
		v.pop_back();
	}
}


int main() {
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> S[i][j];
			totalSum += S[i][j];
		}
	}
	makeTeam(0, 0);
	cout << minDiff;
}

조합과 같은 코드인데 {0, 1, 2}와 같이 한 팀이 만들어지면 0행, 0열, 1행, 1열, 2행, 2열을 전체에서 빼고 중복되어서 빼진 값인 {0, 1, 2}가 만났을 때 생기는 버프 점수를 더해주면 나머지 한 팀의 점수가 나온다.

나는 중간마다 더해서 {0, 1, 2}와 같이 한 팀이 만났을 때 점수가 result에 차곡차곡 더해진다.

 

https://cocoon1787.tistory.com/170

[C/C++] 백준 14889번 - 스타트와 링크 (DFS, 백트래킹, 비트마스킹, 브루트포스)

 

이 분 코드를 보면 나처럼 점수와 노드를 벡터에 저장하는 것이 아니라 한 팀이 된 노드들만 bool 값을 변경해서 팀으로 지정하고 나중에 점수를 구하는 방법도 있다.

40ms가 내가 짠 코드인데 더 이해하기 쉬운 코드로 구현하면 될 것 같다.

 

 

 

21611. (마법사 상어와 블리자드) 마법사 상어는 블리자드를 총 M번 시전했다. 시전한 마법의 정보가 주어졌을 때, 1×(폭발한 1번 구슬의 개수) + 2×(폭발한 2번 구슬의 개수) + 3×(폭발한 3번 구슬의 개수)를 구해보자.

#include<iostream>
#include<vector>
using namespace std;
int N, M;
int x, y;
int A[50][50];
int dx[] = { 0, -1, 1, 0 ,0 };
int dy[] = { 0, 0, 0, -1, 1 };
int movingIdx[] = { 3, 2, 4, 1 }; // 좌, 하, 우, 상
int d;
int s;
int BallsNum;
int ex[4];
void countBall() {
	BallsNum = 0;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (A[i][j] != 0) {
				BallsNum++;
			}
		}
	}
}

int changeDirection(int current, int x, int y, bool visited[][50]) {
	int nextCurrent = (current + 1) % 4;
	int nextD = movingIdx[nextCurrent];
	int nx = x + dx[nextD];
	int ny = y + dy[nextD];
	if (nx <= 0 || nx > N || ny <= 0 || ny > N)
		return current;
	if (visited[nx][ny] == 0)
		return nextCurrent;
	else
		return current;
}

void movingBall() {
	int Balls = BallsNum;
	int repeat = 1;

	while (repeat--) {
		int current = 0;
		int cX = x;
		int cY = y;
		bool visited[50][50] = { 0, };
		int temp = Balls;
		while (temp--) {
			visited[cX][cY] = 1;
			int di = movingIdx[current];
			int fallX = cX + dx[di];
			int fallY = cY + dy[di];
			if (A[cX][cY] == 0) {
				A[cX][cY] = A[fallX][fallY];
				if (A[fallX][fallY] == 0)
					repeat = 1;
				A[fallX][fallY] = 0;
			}
			cX = fallX;
			cY = fallY;
			current = changeDirection(current, cX, cY, visited);
		}
		Balls--; // 한칸씩 이동완료
	}
}

void breakMagic() {
	for (int i = 1; i <= s; i++)
	{
		int nx = x + dx[d]*i;
		int ny = y + dy[d]*i;
		if (nx <= 0 || nx > N || ny <= 0 || ny > N)
			break;
		// 구슬 파괴
		if (A[nx][ny] != 0) {
			A[nx][ny] = 0;
		}
	}
}

bool bomb() {
	int current = 0;
	int temp = BallsNum;
	int cX = x;
	int cY = y;
	bool visited[50][50] = { 0, };
	vector<pair<int, int>>v;
	vector<pair<int, int>>tempV;
	while (temp--) {
		visited[cX][cY] = 1;
		int di = movingIdx[current];
		int nx = cX + dx[di];
		int ny = cY + dy[di];
		if (A[cX][cY] != A[nx][ny]) {
			if (tempV.size() >= 4) {
				v.insert(v.end(), tempV.begin(), tempV.end());
			}
			tempV.clear();
		}
		tempV.push_back({ nx, ny });
		cX = nx;
		cY = ny;
		current = changeDirection(current, cX, cY, visited);
	}
	if (v.size() == 0)
		return false;

	for (int i = 0; i < v.size(); i++)
	{
		for (int j = 0; j < v.size(); j++)
		{
			int r = v[i].first;
			int c = v[i].second;
			ex[A[r][c]]++;
			A[r][c] = 0;
		}
	}
	return true;
}

void newMap(vector<int>ball) {
	int current = 0;
	int temp = N * N;
	int cX = x;
	int cY = y;
	bool visited[50][50] = { 0, };
	int cnt = 1;
	int idx = 1;
	while (temp--) {
		visited[cX][cY] = 1;
		int di = movingIdx[current];
		int nx = cX + dx[di];
		int ny = cY + dy[di];
		if (idx < ball.size()) {
			A[cX][cY] = ball[idx];
			idx++;
		}
		else {
			A[cX][cY] = 0;
		}
		cX = nx;
		cY = ny;
		current = changeDirection(current, cX, cY, visited);
	}
	A[x][y] = -1;
}

void tranform() {
	vector<int>ball;
	int current = 0;
	int temp = BallsNum;
	int cX = x;
	int cY = y;
	bool visited[50][50] = { 0, };
	int cnt = 1;
	while (temp--) {
		visited[cX][cY] = 1;
		int di = movingIdx[current];
		int nx = cX + dx[di];
		int ny = cY + dy[di];
		if (A[cX][cY] != A[nx][ny]) {
			ball.push_back(cnt);
			ball.push_back(A[cX][cY]);
			cnt = 1;
		}
		else {
			cnt++;
		}
		cX = nx;
		cY = ny;
		current = changeDirection(current, cX, cY, visited);
	}
	newMap(ball);
}

int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> A[i][j];
			if (A[i][j] != 0) {
				BallsNum++;
			}
		}
	}
	x = (N + 1) / 2;
	y = (N + 1) / 2;
	A[x][y] = -1;
	for (int i = 0; i < M; i++)
	{
		cin >> d >> s;
		breakMagic();
		movingBall();
		countBall();
		while (bomb()) {
			movingBall();
		}
		tranform();
		countBall();
	}

	cout << ex[1] + 2 * ex[2] + 3 * ex[3];
	return 0;
}

진짜 간신히!!!!!!! 짠 코드라... 사실 다른 분꺼 볼라다가 시도한게 아까워서 끝까지 했다. 운좋게 한번에 통과하긴했는데 아무도 이해못하고 나만 이해되는 코드라서 다른 분 티스토리를 첨부하도록 하겠다.

https://yabmoons.tistory.com/659

[ 백준 21611 ] 마법사 상어와 블리자드 (C++)

빙글빙글 돌면서 계속 접근하지 않고 미리 0부터 N^2-1까지 x, y를 저장해둔게 인상깊었다. 저 방식으로 하면 시간도 훨씬 단축될테니 위 티스토리를 참고하는 것을 추천한다.

i_vec1.insert(i_vec1.end(), i_vec2.begin(), i_vec2.end());

벡터 뒤에 벡터 삽입하려면 insert 사용!

// dq에 3, 1이 들어있던 생태라면
cout<<dq[0]; // 3 출력
dq.insert(dq.begin()+1, 2); // 3, 2, 1이 된다 (원하는 곳의 위치를 넣기)
dq.erase(dq.begin()); // 2, 1이 된다

deque은 인덱스 접근가능!

 

 

 

23288. (주사위 굴리기 2) 보드의 크기와 각 칸에 있는 정수, 주사위의 이동 횟수 K가 주어졌을때, 각 이동에서 획득하는 점수의 합을 구해보자.

#include<iostream>
using namespace std;
int N, M, K;
int map[21][21];
int dx[] = { 0, 1, 0, -1 }; // 오 아 왼 위
int dy[] = { 1, 0, -1, 0 };
int di = 0;
int x = 1, y = 1;
int dice[7];
int cnt;
void movingDice(int di) {
	switch (di)
	{
	case 0: { // 오른쪽
		int temp = dice[3];
		dice[3] = dice[1];
		dice[1] = dice[4];
		dice[4] = dice[6];
		dice[6] = temp;
		break;
	}
	case 1: { // 아래
		int temp = dice[5];
		dice[5] = dice[1];
		dice[1] = dice[2];
		dice[2] = dice[6];
		dice[6] = temp;
		break;
	}
	case 2: { // 왼쪽
		int temp = dice[4];
		dice[4] = dice[1];
		dice[1] = dice[3];
		dice[3] = dice[6];
		dice[6] = temp;
		break;
	}
	case 3: { // 위
		int temp = dice[2];
		dice[2] = dice[1];
		dice[1] = dice[5];
		dice[5] = dice[6];
		dice[6] = temp;
		break;
	}
	}
}

void DiceGame() {
	int nx = x + dx[di];
	int ny = y + dy[di];
	if (nx <= 0 || nx > N || ny <= 0 || ny > M) {
		di = (di + 2) % 4;
		nx = x + dx[di];
		ny = y + dy[di];
	}
	movingDice(di); // 주사위 굴리기
	int A = dice[6];
	int B = map[nx][ny];
	if (A > B)
		di = (di + 1) % 4;
	else if (A < B)
		di = (di + 3) % 4;
	x = nx;
	y = ny;
}

void getScore(int r, int c, bool visited[21][21]) {
	visited[r][c] = 1;
	cnt++;
	for (int i = 0; i < 4; i++)
	{
		int nx = r + dx[i];
		int ny = c + dy[i];
		if (nx <= 0 || nx > N || ny <= 0 || ny > M)
			continue;
		if (visited[nx][ny] == 0 && map[x][y] == map[nx][ny]) {
			getScore(nx, ny, visited);
		}
	}
}

int main() {
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			cin >> map[i][j];
		}
	}

	// 초기 주사위
	for (int i = 1; i < 7; i++)
	{
		dice[i] = i;
	}

	int score = 0;
	while (K--) {
		bool visited[21][21] = { 0, };
		DiceGame();
		getScore(x, y, visited);
		score += map[x][y] * cnt;
		cnt = 0;
	}
	cout << score;
}

점수 획득 조건 이해를 잘못해서 은근 시간이 오래걸렸다. 그냥 해당 칸이랑 똑같은 숫자가 몇개나 연결되어있는지 세면 되는 간단한 component 문제였다. 

 

 

 

23290. (마법사 상어와 복제) 격자에 있는 물고기의 위치, 방향 정보와 상어의 위치, 그리고 연습 횟수 S가 주어진다. S번 연습을 모두 마쳤을때, 격자에 있는 물고기의 수를 구해보자.

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int M, S; // 물고기수, 연습횟수
int dx[] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
int dy[] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
int sX;
int sY;
vector<int> A[5][5];
vector<pair<pair<int, int>, int>>temp;
vector<pair<int, int>> dfs;
vector<pair<int, int>> maxDfs;
bool smell[5][5];
vector<pair<int, int>> smellHistory[101];
int maxAmount = -1;
void findingFish(int x, int y) {

	if (dfs.size() == 3) {
		int sum = 0;
		bool visited[5][5] = { 0, };
		for (int i = 0; i < dfs.size(); i++)
		{
			int x = dfs[i].first;
			int y = dfs[i].second;
			if (visited[x][y] == 0) {
				sum += A[x][y].size();
				visited[x][y] = 1;
			}
		}
		if (maxAmount < sum) {
			maxAmount = sum;
			maxDfs = dfs;
		}
		return;
	}
	if (!(x - 1 <= 0 || x - 1 > 4 || y <= 0 || y > 4)) {
		dfs.push_back({ x - 1, y });
		findingFish(x - 1, y);
		dfs.pop_back();
	}
	if (!(x <= 0 || x > 4 || y - 1 <= 0 || y - 1 > 4)) {

		dfs.push_back({ x, y - 1 });
		findingFish(x, y - 1);
		dfs.pop_back();
	}
	if (!(x + 1 <= 0 || x + 1 > 4 || y <= 0 || y > 4)) {
		dfs.push_back({ x + 1, y });
		findingFish(x + 1, y);
		dfs.pop_back();
	}
	if (!(x <= 0 || x > 4 || y + 1 <= 0 || y + 1 > 4)) {
		dfs.push_back({ x, y + 1 });
		findingFish(x, y + 1);
		dfs.pop_back();
	}

}

void removeSmell(int cnt) {
	if (cnt - 2 < 0)
		return;
	for (int i = 1; i <= 4; i++)
	{
		for (int j = 1; j <= 4; j++)
		{
			smell[i][j] = 0;
		}
	}
	for (int i = 0; i < smellHistory[cnt - 1].size(); i++)
	{
		int x = smellHistory[cnt - 1][i].first;
		int y = smellHistory[cnt - 1][i].second;
		smell[x][y] = 1;
	}
	for (int i = 0; i < smellHistory[cnt].size(); i++)
	{
		int x = smellHistory[cnt][i].first;
		int y = smellHistory[cnt][i].second;
		smell[x][y] = 1;
	}
}

void killFish(int idx) {
	for (int i = 0; i < maxDfs.size(); i++)
	{
		int x = maxDfs[i].first;
		int y = maxDfs[i].second;
		if (A[x][y].size() > 0) {
			smell[x][y] = 1;
			A[x][y].clear();
			smellHistory[idx].push_back({ x, y });
		}
	}

	sX = maxDfs[2].first;
	sY = maxDfs[2].second;
	maxDfs.clear();
	dfs.clear();
	maxAmount = -1;
}


void Copy() {
	temp.clear();
	for (int i = 1; i <= 4; i++)
	{
		for (int j = 1; j <= 4; j++)
		{
			for (int k = 0; k < A[i][j].size(); k++)
			{
				temp.push_back({ { i, j }, A[i][j][k] });
			}
		}
	}
}

void magicCopy() {
	for (int i = 0; i < temp.size(); i++)
	{
		int x = temp[i].first.first;
		int y = temp[i].first.second;
		int d = temp[i].second;
		A[x][y].push_back(d);
	}
}

void movingFish() {
	vector<pair<pair<int, int>, int>>moving;
	for (int i = 0; i < temp.size(); i++)
	{
		int x = temp[i].first.first;
		int y = temp[i].first.second;
		int d = temp[i].second;

		int nx = x + dx[d];
		int ny = y + dy[d];
		if ((nx == sX && ny == sY) || (nx <= 0 || nx > 4 || ny <= 0 || ny > 4) || smell[nx][ny] == 1) {
			bool flag = 0;
			for (int i = 1; i < 9; i++)
			{
				// 반시계 회전	
				d--;
				if (d <= 0)
					d += 8;
				nx = x + dx[d];
				ny = y + dy[d];
				if ((nx == sX && ny == sY) || (nx <= 0 || nx > 4 || ny <= 0 || ny > 4) || smell[nx][ny] == 1)
					continue;
				else {
					flag = 1;
					break;
				}
			}
			if (flag == 0) {
				moving.push_back({ {x, y}, d });
				continue;
			}
		}
		moving.push_back({ {nx, ny}, d });
	}

	for (int i = 1; i <= 4; i++)
	{
		for (int j = 1; j <= 4; j++)
		{
			A[i][j].clear();
		}
	}

	for (int i = 0; i < moving.size(); i++)
	{
		int x = moving[i].first.first;
		int y = moving[i].first.second;
		int d = moving[i].second;
		A[x][y].push_back(d);
	}
}
int main() {
	cin >> M >> S;
	for (int i = 0; i < M; i++)
	{
		int fX, fY, d;
		cin >> fX >> fY >> d;
		A[fX][fY].push_back(d);
	}
	cin >> sX >> sY;

	for (int i = 0; i < S; i++)
	{
		Copy();
		movingFish();
		findingFish(sX, sY);
		killFish(i);
		removeSmell(i);
		magicCopy();

	}

	int sum = 0;
	for (int i = 1; i <= 4; i++)
	{
		for (int j = 1; j <= 4; j++)
		{
			sum += A[i][j].size();
		}
	}

	cout << sum;
}

문제를 잘못이해해서 5시간이나 걸린 문제...

1) 상어는 이동 시작할 때 물고기가 있어도 먹고 시작하지 않는다. (이거 때문에 5시간이나 걸렸다)

2) 상어는 왔던 곳을 또 올 수 있다. (visited를 dfs 자체에서는 사용하지 않는다는 뜻이다.)

문제 이해만 바로 했어도 금방 풀었을텐데... 슬펐다

 

 

 

 

어항 정리랑 온풍기 안녕!도 시도해보려고 했는데 시간이 부족해서 일단 패스하도록 하겠다. 만약 이번에 취업을 못한다면 온풍기 안녕이랑 어항 정리 문제풀러 올 예정이다...^^ ㅋ... 오기 싫어도 와야댐...

마법사 상어는 여기서 끝!