기록을

https://www.acmicpc.net/problem/2210

5 * 5의 격자판이 주어진다.

그 격자판에 있는 정수들을 활용해서 길이 6의 수열을 만들어야 한다.

이 때 사용했던 숫자라도 중복해서 사용할 수 있다.

또한, 숫자는 직전에 선택했던 숫자의 동서남북 방향에 위치한 숫자중에 하나로 선택해야 한다.

중복 제거를 간편하게 하기 위해서 set을 사용했다.

https://www.acmicpc.net/problem/14889

순열과 조합을 적절히 사용해주면 되는 문제였다.

먼저 팀을 나누기 위해서는 순서는 중요하지 않기 때문에 조합으로 뽑는다.

0, 1, 2, 3, 4, 5 이렇게 6명의 사람이 있으면 조합으로 3개를 뽑아서 두 개의 팀을 만들어 준다.

이어서 팀 각각에 대해서 보자.

예를 들어 스타트 팀이 0, 1, 2로 결정되면 링크 팀은 자연스럽게 3, 4, 5로 결정된다.

이제 팀 각각에 대해서 점수를 계산해주면 된다.

S01과 S10이 다르다고 했다. 따라서 스타트팀의 경우에 대해서 순열로 뽑아준다. 총 3P2가지가 나올 것이다.

이를 더해서 점수 하나를 만들어주고, 링크팀에 대해서도 진행해준다. 이제 점수차이의 최솟값을 찾으면 된다.

점수 계산시 순열을 사용하지 않고, 조합으로 뽑은 이후에, 순서를 뒤집어서 계산을 추가해줘도 동일한 결과가 나온다. 하지만 순열로 처리하면 한 번에 처리할 수 있기 때문에 순열을 사용했다.

https://www.acmicpc.net/problem/15683

문제를 보면, 카메라의 전체 개수가 8개로 많지 않다. 카메라의 종류별로 가능한 각도들을 모두 시뮬레이션해주면 되겠다.

각각의 카메라가 가질 수 있는 상태를 번호로 지정했다. 1번 카메라는 0~3번 상태, 2번 카메라는 4번~5번 상태... 이런 방식이다.

이제 카메라들이 띄고 있을 수 있는 상태를 조합으로 뽑아주면 된다.

이때 1번 카메라는 0~3번 밖에 쓸 수 없는 것처럼, 각 카메라별로 가능한 상태(인덱스)가 정해져 있기 때문에, 조합을 카메라에 대해서 먼저 해주고, 그리고 카메라의 상태에 대해서 이어서 해주어야한다.

작게 동, 서, 남, 북 방향으로 뻗어가는 방식인데, 카메라에 따라서 동시에 동서, 동남, 동서남 이런식으로 여러가지 상태를 가진다.

즉 동, 서, 남, 북 네가지 방향에 대한 처리만 정확하게 구현하면, 나머지는 그냥 그대로 코드를 사용하면 된다.

https://www.acmicpc.net/problem/14502

조합과 bfs가 합쳐진 문제인 연구소 시리즈의 첫번째 문제이다.

다른 연구소 문제를 해결했다면, 비슷한 아이디어로 무난하게 해결할 수 있다.

알고리즘은 다음과 같다.

1. 빈 공간(0인 위치)를 벡터에 모두 담아놓고 그 중 세개를 조합으로 뽑는다.

2. 조합으로 뽑은 곳의 값을 1로 (벽으로) 변경해준 이후에 bfs를 수행한다.

3. 방문되지 않은 지점(바이러스가 퍼지지 않은 지점)이면서 빈 공간인 부분의 수를 계산한다.

4. 수정한 map과 방문처리 배열을 초기화 시켜준다.

https://www.acmicpc.net/problem/15686

비교적 간단한 조합 / 백트래킹 / 전수조사 문제이다.

문제를 보면, 결국 모든 경우의 수를 조사해야 하는 상황이다. 따라서 집의 위치와, 치킨집의 위치를 따로 벡터에 담아주고,

백트래킹을 활용해서 치킨집을 m개 선택한 다음, 선택한 치킨집을 가지고 치킨 거리를 구하면 되겠다.

이 경우에 다시 일반 가정집을 검색할 필요가 없도록, 미리 초반에 일반집도 벡터에 담아두고 사용하면 되겠다.

[소스코드]

https://www.acmicpc.net/problem/17141

연구소 3을 해결했다면 거저 먹을 수 있는 문제이다.

기본적으로 바이러스의 후보지들을 가지고 조합을 구해야 한다.

바이러스 후보지가 5곳이고 m = 3으로 주어진다면, 5Cm만큼의 경우의 수를 확인해보면 답을 찾을 수 있다.

https://www.acmicpc.net/problem/17142

문제 설명

1. 비활성 바이러스의 위치가 여러곳 주어진다.

2. 그 중에서 M개를 선택해서 확산 바이러스로 만들고, 바이러스의 확산을 시작한다.

(확산 바이러스는 비활성 바이러스를 만나면 그 비활성 바이러스를 확산 바이러스로 바꾼다)

3. 바이러스가 전부 퍼질 때까지 걸린 시간의 최솟값을 구하여라.

문제를 시작하기 전에 몇가지 표현을 잘 이해하고 들어가야한다.

먼저 문제가 구하라고 한 것은, 바이러스가 다 퍼질 때까지 걸린 최소 시간이다. 퍼지는 바이러스가 활성 바이러스여야 한다는 말은 없다.

테스트케이스를 좋게 주지 않았더라면 괴랄한 정답률을 보여주지 않았을까 생각한다.

아래쪽에 있는 테스트 케이스를 활용하면 대부분의 엣지 케이스에 대한 감을 잡을 수 있을 것이다.

[알고리즘]

1. 백트레킹을 활용해서 전체 바이러스 중에서 m개를 선택한다.

2. 선택한 m개의 바이러스를 큐에 넣고 BFS를 돌린다.

3. 빈칸과 비활성 바이러스가 있으면서 방문하지 않은 지점이면 바이러스를 확산시키고, 시간을 기록한다.

4. 시간이 얼마 걸렸는지 파악하기 위해 방문처리 배열 내에서 최댓값을 찾는다. 이 때 최댓값을 선택할 때 그 지점이 바이러스가 위치하고 있는 지점이라면 최댓값으로 보지 않는다.

마지막 테스트 케이스에서와 같이, 이미 바이러스로 채워져있는 곳은 사실 방문할 필요가 없었던 지점이다. 하지만 거쳐가면서 확산이 이루어져야 하기 때문에 일단 채택은 하고, 바이러스가 전체로 퍼지는 시간에는 영향을 끼치면 안되기 때문에 제외해준다.

5. 위에서 구한 최댓값(시간)의 최솟값을 답으로 정한다.

#include<iostream>
#include<vector>
#include<queue>
#include<limits.h>
using namespace std;

int n, m, map[51][51], dis[51][51], arr[11], st = 0; //연구소 크기, 바이러스 개수
bool isused[11];
struct VIRUS {
	int r;
	int c;
};
vector<VIRUS> v;
queue<pair<int, int> > q;
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
int res = INT_MAX;

void bfs() {
	
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();
		
		for (int i = 0; i < 4; i++) {
			int nr = cur.first + dr[i];
			int nc = cur.second + dc[i];
			if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
			if (dis[nr][nc] >= 0 || map[nr][nc] == 1) continue;
			
			q.push({ nr, nc });
			dis[nr][nc] = dis[cur.first][cur.second] + 1;
		}
	}
}
void init() {
	for(int i = 0 ; i < n ; i++)
		for (int j = 0; j < n; j++) 
			dis[i][j] = -1;
}
bool isDone(){
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (dis[i][j] == -1 && map[i][j] != 1)
				return false;
		}
	}
	return true;
}
void findMax() {
	int Max = 0;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) 
			if (Max < dis[i][j] && map[i][j] != 2) 
				Max = dis[i][j];

	if (res > Max) res = Max;
}
void func(int k) {
	if (k == m) {

		for (int i = 0; i < m; i++) {
			int r = v[arr[i]].r;
			int c = v[arr[i]].c;
			q.push({ r, c });
			dis[r][c]++;
		}
		bfs();

		if (isDone()) 
			findMax();
		
		init();

		return;
	}

	if (k == 0) st = 0;
	for (int i = st; i < v.size(); i++) {
		if (!isused[i]) {
			arr[k] = i;
			st = i;
			isused[i] = true;
			func(k + 1);
			isused[i] = false;
		}
	}
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			dis[i][j] = -1;
			if (map[i][j] == 2) { //바이러스 위치 저장
				VIRUS tmp;
				tmp.r = i;
				tmp.c = j;
				v.push_back(tmp);
			}
		}

	func(0);

	if (res == INT_MAX) cout << -1 << '\n';
	else
		cout << res;
	return 0;
}

https://www.acmicpc.net/problem/17281

선수 9명의 순서를 결정해야 한다. 4번 타자는 1번 선수로 고정되어 있기 때문에 이를 반영해준다.

이닝별로 선수들의 결과를 입력으로 받는다.

따라서 모든 순열을 구해서 선수들의 순서를 만들어낸 이후에, 야구의 조건을 구현해주면 된다.

1루, 2루 등에 진출해 있는 선수들에 대한 관리는, 선수 번호를 그대로 인덱스로 해서 배열을 두었다.

1이면 1루에 있다는 뜻이고, 2면 2루 3이면 3루에, 

4 이상이 되면 홈으로 들어왔다는 의미이다.

각 이닝별로 선수들의 수행을 그대로 따라가면서 시뮬레이션을 진행해주면 된다.

res[][] 배열은 이닝별 선수의 득점이다.

num은 1~9까지 선수들 중에 9명을 뽑는 경우의 수로 사용한다.

ord는 뽑아서 결정된 선수들의 순서이다. ord[i]는 i번 타자를 의미한다.

#include<iostream> //2백만
#include<vector>
using namespace std;
int n, res[52][10], num[10], ord[10], pos[10], Max = -1;
bool isused[10];
void play() {
	int hitter = 1, score = 0;
	for (int i = 1; i <= n; i++) { //i이닝에
		int outCnt = 0;

		while (1) {
			if (res[i][ord[hitter]] == 0) { //아웃인 경우
				hitter++;
				if (hitter >= 10) hitter = 1;
				outCnt++;
				if (outCnt == 3) {
					//이닝 교체
					for (int j = 1; j <= 9; j++) pos[j] = 0;
					break;
				}
			}
			else {
				//득점타
				for (int j = 1; j <= 9; j++) {
					if (pos[j] > 0 || j == ord[hitter]) { //타석에 나가 있는 선수라면
						pos[j] += res[i][ord[hitter]];
						if (pos[j] >= 4) {
							//홈에 들어오면
							pos[j] = 0;
							score++;
						}
					}
				}
				hitter++;
				if (hitter >= 10) hitter = 1;
			}
		}
	}
	if (Max < score) Max = score;
}
void func(int k) {
	if (k > 9) { //base condition
		play();
		return;
	}
	for (int i = 2; i <= 9; i++) {
		if (!isused[i]) {
			ord[k] = i;
			isused[i] = true;
			if (k == 3) func(k + 2); //3번엔 다음 4번이 아니라 5번을 정함
			else func(k + 1);
			isused[i] = false;
		}
	}
}
int main(void) {
	for (int i = 1; i <= 9; i++)
		num[i] = i;
	isused[1] = true; //1은 항상 사용중
	ord[4] = 1; // 4번 선수는 항상 1
	cin >> n;
	
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= 9; j++) 
			cin >> res[i][j];
	
	func(1);
	cout << Max << '\n';
	return 0;
}

https://www.acmicpc.net/problem/1799

흑과 백으로 칸을 구분한다.

1을 흑 0을 백이라고 하면

1 0 1 0

0 1 0 1

1 0 1 0

0 1 0 1

이런식으로 체스판이 이루어져있다고 생각하고 흑은 흑대로 먼저 처리하고, 백은 백대로 먼저 처리하는 것이다.

개인적으로 굉장히 해내기 어려운 발상이라고 생각한다.

#include<iostream>
using namespace std;
int n, m[10][10];
int cnt = 0, Bmax = 0, Wmax = 0;
bool isused1[20], isused2[20];
void Black(int row, int col, int cnt) {
	if (col >= n) {
		row++;
		if (row % 2 == 0) col = 0;
		else
			col = 1;
	}
	if (Bmax < cnt) Bmax = cnt;
	if (row >= n) return;
	
	if (m[row][col] == 1 && !isused1[row + col]
		&& !isused2[row - col + n - 1]) {
		isused1[row + col] = true;
		isused2[row - col + n - 1] = true;
		Black(row, col + 2, cnt + 1); //(r,c)가 가능한 지점일 때
		isused1[row + col] = false;
		isused2[row - col + n - 1] = false;
	}
	Black(row, col + 2, cnt);
}
void White(int row, int col, int cnt) {
	if (col >= n) {
		row++;
		if (row % 2 == 0) col = 1;
		else
			col = 0;
	}
	if (Wmax < cnt) Wmax = cnt;
	if (row >= n) return;

	if (m[row][col] == 1 && !isused1[row + col]
		&& !isused2[row - col + n - 1]) {
		isused1[row + col] = true;
		isused2[row - col + n - 1] = true;
		White(row, col + 2, cnt + 1); //(r,c)가 가능한 지점일 때
		isused1[row + col] = false;
		isused2[row - col + n - 1] = false;
	}
	White(row, col + 2, cnt);
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> m[i][j];
	

	Black(0, 0, 0);
	for (int i = 0; i < 2 * n - 1; i++) {
		isused1[i] = false;
		isused2[i] = false;
	}
	White(0, 1, 0);
	cout << Wmax + Bmax << '\n';
}

https://www.acmicpc.net/problem/1799

이 문제를 무작정 n^2으로 풀면 TLE를 받는다.

아래는 시간초과가 나는 코드이다.

한 대각선에 비숍은 하나밖에 존재할 수 없다는 것을 이용하면 복잡도를 2n-1 즉 n으로 떨어트릴 수 있을 것이다.

#include<iostream>
using namespace std;
int n, m[10][10];
int cnt = 0, Max = 0;
bool isused1[10], isused2[10];
void func(int k) {
	
	if (Max < k) Max = k;

	bool isExist1 = false , isExist2 = false;
	for (int i = 0; i < 10; i++) {
		if (!isused1[i]) {
			isExist1 = true;
			break;
		}
		if (!isused2[i]) {
			isExist2 = true;
			break;
		}
	}

	if (!isExist1 && !isExist2) return;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (m[i][j] == 1 && !isused1[i + j] &&
				!isused2[i - j + n - 1]) {
				//cnt++;
				isused1[i + j] = true;
				isused2[i - j + n - 1] = true;
				func(k + 1);
				isused1[i + j] = false;
				isused2[i - j + n - 1] = false;
			}
		}
	}
	return;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> m[i][j];
	
	func(0);
	cout << Max << '\n';
}