코딩하는 두꺼비

www.acmicpc.net/problem/15686

재귀로 풀지 조합으로 풀지 고민하다가 조합으로 푼 문제이다. 다른 사람들 풀이를 보니 재귀로 많이 풀어낸 것 같다.

단순히 치킨거리를 구하는 게 아니라 치킨집을 몇개 선정하고 최소 치킨 거리를 구해야 해서 조금 까다로웠다.

처음에 모든 치킨 거리의 수를 계산해서 배열에 저장하고 M개의 치킨집은 벡터에 0 나머지는 1을 넣고 그 조합벡터를

next_permutation을 사용해 풀어냈다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M, ans = 99999;
int map[51][51];
vector<pair<int, int>> home;
vector<pair<int, int>> chick;
int htoc[101][14];
vector<int> open;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int tmp, tmp2;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			if (map[i][j] == 1) {
				home.push_back({ i,j });
			}
			if (map[i][j] == 2) {
				chick.push_back({ i,j });
			}
		}
	}
	for (int i = 0; i < home.size(); i++) {
		for (int j = 0; j < chick.size(); j++) {
			htoc[i][j] = abs(home[i].first - chick[j].first) + abs(home[i].second - chick[j].second);
		}
	}
	for (int i = 0; i < chick.size(); i++) {
		if (i < M) {
			open.push_back(0);
		}
		else {
			open.push_back(1);
		}
	}
	do {
		tmp2 = 0;
		for (int i = 0; i < home.size(); i++) {
			tmp = 9999;
			for (int j = 0; j < chick.size(); j++) {
				if (open[j] == 0) {
					tmp = min(tmp, htoc[i][j]);
				}
			}
			tmp2 += tmp;
		}
		ans = min(tmp2, ans);
	} while (next_permutation(open.begin(), open.end()));

	cout << ans;
	return 0;
}

www.acmicpc.net/problem/15683

처음에 단순히 각각의 최대값들만 계산하게 구현했다가 안되서 한동안 코테 공부를 소홀하게 만든 문제이다..

단순 구현 문제임에도 고려해야 될 사항들이 많은 문제라 많이 어려웠다.(내 생각엔 최악의 문제이다..ㅠㅠ)

고민하다가 결국 재귀로 해결할 수 있었고 모든 경우의 수를 브루트 포스와 비슷하게 다 고려하여 풀었다.

각 cctv의 시야 범위를 7로 바꾸는 부분은 바킹독님의 풀이를 참고하여 수정하였다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

int N, M, ans = 987654;

int map2[10][10];
int cam2[2][2] = { {1,3},{2,4} };
int cam3[4][2] = { {1,2},{2,3},{3,4},{1,4} };
int cam4[4][3] = { {1,2,3},{2,3,4},{1,3,4},{1,2,4} };
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1,0 };
vector<pair<int, int>> v;


void cpy(int(*map1)[10]) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			map2[i][j] = map1[i][j];
		}
	}
}

void cpy2(int (*map1)[10]) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			map1[i][j] = map2[i][j];
		}
	}
}

void check(int x, int y, int dir) {
	while (1) {
		x += dx[dir-1];
		y += dy[dir-1];
		if (x < 0 || y < 0 || x >= N || y >= M || map2[x][y] == 6) {
			return;
		}
		if (map2[x][y] != 0) {
			continue;
		}
		map2[x][y] = 7;
	}
}

void dfs(int cnt) {
	int map1[10][10];
	cpy2(map1);
	if (cnt == v.size()) {
		int k = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map2[i][j] == 0) {
					k++;
				}
			}
		}
		ans = min(ans, k);
		return;
	}
	
	int x = v[cnt].first;
	int y = v[cnt].second;
	if (map2[x][y] == 1) {
		for (int i = 1; i <= 4; i++) {
			cpy2(map1);
			check(x, y, i);
			cnt++;
			dfs(cnt);
			cnt--;
			cpy(map1);
		}
	}
	else if (map2[x][y] == 2) {
		for (int i = 0; i < 2; i++) {
			cpy2(map1);
			for (int j = 0; j < 2; j++) {
				check(x, y, cam2[i][j]);
			}
			cnt++;
			dfs(cnt);
			cnt--;
			cpy(map1);
		}
	}
	else if (map2[x][y] == 3) {
		for (int i = 0; i < 4; i++) {
			cpy2(map1);
			for (int j = 0; j < 2; j++) {
				check(x, y, cam3[i][j]);
			}
			cnt++;
			dfs(cnt);
			cnt--;
			cpy(map1);
		}
	}
	else if (map2[x][y] == 4) {
		cpy2(map1);
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 3; j++) {
				check(x, y, cam4[i][j]);
			}
			cnt++;
			dfs(cnt);
			cnt--;
			cpy(map1);
		}
	}
	else {
		cpy2(map1);
		for (int i = 1; i <= 4; i++) {
			check(x, y, i);
		}
		cnt++;
		dfs(cnt);
		cnt--;
		cpy(map1);
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map2[i][j];
			if (map2[i][j] != 0 && map2[i][j] != 6) {
				v.push_back({ i,j });
			}
		}
	}
	dfs(0);
	
	cout << ans;
}

www.acmicpc.net/problem/14499

처음엔 어떻게 풀어야할지 아예 감이 안잡히는 문제였다.

주사위를 구현해야하는데 방향까지 고려해서 구현을 해야한다고 생각을 했었다.

하지만 전개도 번호를 고정으로 잡고 그 안의 값들만 변경 시켜서 구현하니 바로 풀리는 문제였다.

각각 동서남북으로 이동하면서 조건 확인 및 좌표수정, 주사위 바닥면을 복사해주고, 주사위 면들을 옮겼다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M, x, y, K;
int map[21][21];
int dice[7];

void cp(int a) {	//주사위 바닥면 복사
	if (map[x][y] == 0) {
		map[x][y] = dice[a];
	}
	else {
		dice[a] = map[x][y];
		map[x][y] = 0;
	}
}

int main() {
	int z, tmp;
	cin >> N >> M >> x >> y >> K;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < K; i++) {
		cin >> z;
		if (z == 1) {	//동쪽 이동
			if (y + 1 < M) {
				y++;
				cp(3);
				tmp = dice[1];
				dice[1] = dice[3];
				dice[3] = dice[6];
				dice[6] = dice[4];
				dice[4] = tmp;
				cout << dice[6] << "\n";
			}
		}
		else if (z == 2) {	//서쪽 이동
			if (y - 1 >= 0) {
				y--;
				cp(4);
				tmp = dice[1];
				dice[1] = dice[4];
				dice[4] = dice[6];
				dice[6] = dice[3];
				dice[3] = tmp;
				cout << dice[6] << "\n";
			}
		}
		else if (z == 3) {		//북쪽 이동
			if (x - 1 >= 0) {
				x--;
				cp(2);
				tmp = dice[1];
				dice[1] = dice[2];
				dice[2] = dice[6];
				dice[6] = dice[5];
				dice[5] = tmp;
				cout << dice[6] << "\n";
			}
		}
		else {
			if (x + 1 < N) {	//남쪽 이동
				x++;
				cp(5);
				tmp = dice[1];
				dice[1] = dice[5];
				dice[5] = dice[6];
				dice[6] = dice[2];
				dice[2] = tmp;
				cout << dice[6] << "\n";
			}
		}
	}
	return 0;
}