백준 17136번 색종이 붙이기 (c++)

풀이도 구현도 무난하게 쉬워서 골드 3정도 되는 문제 아닌가 싶었는데

종료조건을 잘 생각해야 시간초과를 면할 수 있는 문제였다.

 

 

vector<vector<int>> mp;
vector<int> paper(6, 0);

int ans = 210000000;
int cntOne = 0;

10x10 종이의 상태를 저장할 배열

각 크기의 색종이 가 몇개 쓰였는지 저장할 배열

정답을 저장할 변수

재귀함수 종료를 빠르게 판단 할 수 있도록 색종이 를 붙여야 할 갯수를 저장 할 변수

 

bool isComplete(vector<vector<int>> &arr)
{
	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			if (arr[i][j] == 1) return false;
		}
	}
	return true;
}

만들어진 종이판이 정답으로 적합한지 판단한다.

색종이 를 붙여야 할 칸이 한칸이라도 남아있으면 실패

 

bool isStick(vector<vector<int>> &arr, int x, int y, int n)
{
	for (int i = y; i < y + n; i++)
	{
		for (int j = x; j < x + n; j++)
		{
			if (i < 0 || i >= 10 || j < 0 || j >= 10) return false;
			if (arr[i][j] != 1) return false;
		}
	}
	return true;
}

vector<vector<int>> OnStick(vector<vector<int>> arr, int x, int y, int n)
{
	for (int i = y; i < y + n; i++)
	{
		for (int j = x; j < x + n; j++)
		{
			arr[i][j] = 2;
		}
	}
	return arr;
}

 

순회하며 색종이 를 붙여야 할 칸에 n크기의 색종이 를 붙일수 있는지 판단하고

판에 실제로 붙인다.

 

void sol(vector<vector<int>> arr,int lv, int cnt)
{
	if (lv >= ans) return;
	if (cnt == 0)
	{
		if (isComplete(arr) == true)
		{
			ans = min(ans, lv); 
			return;
		}
	}
	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			if (arr[i][j] == 1)
			{
				for (int k = 5; k > 0; k--)
				{
					if (paper[k] >= 5)continue;
					if (isStick(arr, j, i, k) == true)
					{
						paper[k]++;
						sol(OnStick(arr, j, i, k), lv + 1, cnt - k * k);
						paper[k]--;
					}
				}
				return;
			}
		}
	}
}

재귀 레벨은 색종이를 몇개 붙였는지 나타내는것이다.

즉 현재 저장된 최소 색종이 의 갯수보다 더 깊이 들어가려는 것 같으면 의미 없는 연산이므로 반환

 

색종이 를 붙여야 할 칸의 수 cnt가 0이 되면 현재 종이의 상태를 검사한 후

모든 칸이 적절하면 정답을 갱신해준다.

 

종이의 모든 칸을 순회하며 색종이 를 붙여야할 칸(1)을 만나면 각종 크기의 색종이를 붙여본다.

한 종류의 색종이가 5개를 초과하지 않도록 주의한다.

붙여도 된다고 판단되면 종이의 카운트를 올려주고, 색종이를 붙여주고, 재귀에 들어간다.

 

여기서 색종이를 12345다 대봤으면 다음칸으로 이동할 필요 없이 바로 리턴해주는것이 중요하다.

색종이 를 한장이라도 붙였으면 다음 재귀에서 다음칸을 검사할 것이므로 현재 재귀에서 다음칸으로 이동하는 의미는 없다.

또한 어떤 크기의 색종이도 붙이지 못했다면 해당 칸은 채울 방법이 없기에 그 판 자체가 허수가 되어 더이상 진행할 의미도 없어진다.

 

signed main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	for (int i = 0; i < 10; i++)
	{
		vector<int> tmp;
		for (int j = 0; j < 10; j++)
		{
			int a;
			cin >> a;
			if (a == 1) cntOne++;
			tmp.push_back(a);
		}
		mp.push_back(tmp);
	}
	if (cntOne == 0)
	{
		cout << 0 << endl;
		return 0;
	}
	

	sol(mp, 0, cntOne);
	if (ans == 210000000)
	{
		cout << -1 << endl;
	}
	else cout << ans << endl;
	
}

스티커를 붙여야 할 칸이 한칸도 없으면 바로 0을 출력하고 리턴,

정답 변수가 초기값 그대로 나왔으면 스티커를 붙이는게 불가능하다는 뜻이므로 -1 출력