[백준/BOJ] 백준 25241번 : 가희와 사직 구장

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

25241번: 가희와 사직 구장

 

삼총사의 위치가 될 지점을 정해서, 해당 삼총사가 인접하는지 확인하며 삼총사로 인해 얻어지는 값을 구하고, 삼총사 위치를 제외한 남은 위치들 중 점수의 상위 N-3 개의 점수를 구해서 삼총사가 아닌 다른 멤버들로 인해 얻어지는 최댓값을 구하여 문제를 해결했다.

 

삼총사의 위치를 구하는 방법은 이전 삼총사의 위치 행의 오른쪽 열이나, 아래쪽 모든 행의 모든 열을 확인하는 방법으로 삼총사의 위치를 선택했다.

 

코드

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

int r, c, n;
int board[205][205];
vector<int> adds;

vector<int> board_values;
vector<int>::iterator it1;
vector<int>::iterator it2;

int dxdy[8][2] = { {0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1} };
int result = 0;

bool Check(pair<int, int> here, pair<int, int> there) {

	for (int dir = 0; dir < 8; dir++) {
		pair<int, int> check_there = make_pair(here.first + dxdy[dir][0], here.second + dxdy[dir][1]);

		if (check_there == there) {
			return true;
		}
	}

	return false;
}

void Solve(vector<pair<int, int>>& selected, pair<int, int> point)
{
	//3총사의 위치를 다 골랐을때
	if (selected.size() == 3) {

		int this_3_add = 0;
		int this_3_area = 0;
		int temp_result1 = 0; //삼총사로 인해 얻어지는 값
		int temp_result2 = 0; //삼총사 외의 인원으로 인해 얻어지는 값

		int add_index = 0;

		for (int i = 0; i < 3; i++) {

			this_3_area += board[selected[i].first][selected[i].second]; //무대 지점의 값

			for (int j = i + 1; j < 3; j++) {
				if (Check(selected[i], selected[j])) {
					this_3_add += adds[add_index]; //인접해서 더해지는 값
					add_index++;
				}
			}
		}

		temp_result1 = this_3_add + this_3_area;

		//삼총사 위치(selected) 값이 상위 n개의 지점에 속하는지 주의

		vector<int> erased_check(board_values.size(), 0);

		for (int i = 0; i < selected.size(); i++) {
			it1 = lower_bound(board_values.begin(), board_values.end(), board[selected[i].first][selected[i].second]);
			it2 = upper_bound(board_values.begin(), board_values.end(), board[selected[i].first][selected[i].second]);

			int erase_index = it1 - board_values.begin();

			while (erased_check[erase_index] != 0) {
				erase_index++;
			}

			erased_check[erase_index] = 1;
		}


		int add_cnt = 0;
		int add_index2 = board_values.size() - 1;
		temp_result2 = 0;

		while (add_cnt < n - 3) {

			if (erased_check[add_index2] == 1) {
				add_index2--;
				continue;
			}

			temp_result2 += board_values[add_index2];
			add_index2--;
			add_cnt++;
		}

		int temp_result = temp_result1 + temp_result2;
		result = max(result, temp_result);

		return;
	}

	if (point.first >= r) {
		return;
	}

	//point행을 선택하는 경우
	for (int j = point.second; j < c; j++) {
		pair<int, int> here = make_pair(point.first, j);

		pair<int, int> next_point = make_pair(here.first, here.second + 1);
		if (next_point.second >= c) {
			next_point = make_pair(here.first + 1, 0);
		}

		selected.push_back(here);
		Solve(selected, next_point);
		selected.pop_back();
	}

	//point 아래에 있는 행을 선택하는 경우
	for (int i = point.first + 1; i < r; i++) {
		for (int j = 0; j < c; j++) {
			pair<int, int> here = make_pair(i, j);

			pair<int, int> next_point = make_pair(here.first, here.second + 1);
			if (next_point.second >= c) {
				next_point = make_pair(here.first + 1, 0);
			}

			selected.push_back(here);
			Solve(selected, next_point);
			selected.pop_back();
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> r >> c >> n;

	for (int i = 0; i < 3; i++) {
		int input;
		cin >> input; //입력 받지만 사용하지 않음
	}

	for (int i = 0; i < 3; i++) {
		int input;
		cin >> input;

		adds.push_back(input);
	}
	sort(adds.begin(), adds.end());
	reverse(adds.begin(), adds.end()); //큰 순으로 정렬

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			int input;
			cin >> input;

			board[i][j] = input;
			board_values.push_back(input);
		}
	}

	sort(board_values.begin(), board_values.end());

	vector<pair<int, int>> selected;
	Solve(selected, make_pair(0, 0));

	cout << result;

	return 0;
}