[ boj : 1101 ] 스티커 정리1

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

1101번: 스티커 정리 1

(앞으로 문제 생략하겠습니다....ㅠ)

 

해설 : 처음에 n을 생각을 안하고 그냥 뇌를 비우고 permutation을 사용을 했는데 당연히 터지죠...O(50!)...;;

그래서 다른 방법을 사용해야 되는데, 경험상 주의해야 할 부분은 가장 많은 종류의 색을 담고 있는 상자가 반드시 조커상자가 되는게 최선의 선택이라는 것을 보장할 수 없다는 것입니다.

 

왜냐하면 어떤 한상자에서 스티커를 옮길때 어느 제약도 없이 옮길 수 있기 때문입니다.

이를 유의하고 문제에 접근하면, 그냥 n 개의 상자를 전부 한번씩 조커 상자라고 가정을 해볼 수 있는 것이죠.

그리고 이제 나머지 상자들에서 어떻게 옮겨줄 것인가를 찾아야 되는데

 

곰곰이 생각해보면 만약 상자에 2가지 이상의 색의 스티커가 존재한다면 무조건 이 상자에서 `움직임`이 발생해야 합니다. 그러면 2 이상의 스티커를 가지고 있는 상자는 count 시켜줍니다.

 

그리고 0개의 스티커를 가지고 있으면 아무런 조치를 취해주지 않아도 되죠. 그냥 pass 합니다.

 

문제는 스티커가 단 1개 있을 경우인데, 만약 현재 상자를 확인하기 전에 전의 상자들 중에서 동일한 색의 스티커가 존재한다면 이는 `움직임`이 필요한 상자라는 뜻이 됩니다.

 

예를 들어서 

3 3

1 1 1

0 0 1

0 0 1

이런 케이스일때 첫번째 상자를 조커로 지정했다고 하면, 두번째 상자와 세번째 상자중 반드시 하나의 상자에서 `움직임`이 발생해야 됩니다.

 

그럼 다 끝났습니다. 코드로 차분히 옮겨봅시다.

 

#include<bits/stdc++.h>

using namespace std;

int n, m;
int arr[50][50],cnt[50],visit[50];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j])cnt[i]++;
		}
	int ans = n;
	for (int i = 0; i < n; i++) {
		int rev = 0;
		memset(visit, 0, sizeof(visit));
		for (int j = 0; j < n; j++) {
			if (i == j)continue;
			if (cnt[j] > 1) rev++;				
			else if (cnt[j] == 0)continue;
			else {
				bool flag = false;
				for (int k = 0; k < m; k++)
					if (arr[j][k] && !visit[k]) {
						visit[k] = 1;
						flag = !flag;
						break;
					}
				if (!flag)rev++;
			}
		}
		ans = min(ans, rev);
	}
	cout << ans;
	return 0;
}