[백준/BOJ] 백준 1014번 : 컨닝

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

1014번: 컨닝

 

int cache[10][1 << 10]를 통해, cache[i][j] = i행이 j상황(해당 행의 학생 배치 상태를 비트로 표현)일 때 해당 행 이하에서 배치할 수 있는 최대 학생 수를 나타내었으며, 각 row, col에 before_status(이전 행의 학생 배치 상태), here_status(지금 행의 학생 배치 상태) 상태일 때 학생 배치를 고려하는 방법으로 문제를 해결했다.

 

코드

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

int tc;
int n, m;
vector<string> check;
int cache[10][1 << 10]; //cache[i][j] = i행이 j상황일때 해당 행 이하에서 배치할 수 있는 최대 학생수

void Pre()
{
	check.clear();

	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < (1 << 10); j++)
			cache[i][j] = -1;
	}
}

int Solve(int row, int col, int before_status, int here_status, int cnt)
{
	//here_status가 만들어졌을때 (한 행이 다 만들어 졌을때)
	if (col == m)
	{
		int& ret = cache[row][here_status];

		if (ret != -1)
			return ret;

		//현재 행이 마지막 행일때
		if (row == n - 1)
			ret = cnt;

		else
			ret = cnt + Solve(row + 1, 0, here_status, 0, 0);

		return ret;
	}

	//here_status가 아직 만들어지지 않았을때
	//col를 선택하는 경우와 선택하지 않는 경우비교

	//[row][col]위치가 앉을수 없는 위치일때
	if (check[row][col] == 'x')
	{
		return Solve(row, col + 1, before_status, here_status, cnt);
	}


	//첫 열이 아닐때
	if (col != 0)
	{
		//왼쪽에 학생이 있어서 해당 위치에 학생을 배치할 수 없을때
		if ((here_status & (1 << (m - 1 - col + 1))) != 0)
		{
			return Solve(row, col + 1, before_status, here_status, cnt);
		}


		//왼쪽 대각선에 학생이 있어서 해당 위치에 학생을 배치할 수 없을때
		if ((before_status & (1 << (m - 1 - col + 1))) != 0)
		{
			return Solve(row, col + 1, before_status, here_status, cnt);
		}
	}


	if (col != m - 1)
	{
		//오른쪽 대각선에 학생이 있어서 해당 위치에 학생을 배치할 수 없을때
		if ((before_status & (1 << (m - 1 - col - 1))) != 0)
		{
			return Solve(row, col + 1, before_status, here_status, cnt);
		}

	}

	//해당위치에 학생을 배치하는것과 배치하지 않는것 비교
	return max(Solve(row, col + 1, before_status, here_status, cnt), Solve(row, col + 1, before_status, here_status | (1 << m - 1 - col), cnt + 1));
}

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

	cin >> tc;

	for (int t = 0; t < tc; t++)
	{
		Pre();

		cin >> n >> m;

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

			check.push_back(input);
		}

		cout << Solve(0, 0, 0, 0, 0) << "\n";
	}

	return 0;
}