취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1101번 문제인 스티커 정리 1이다.
문제는 아래 링크를 확인하자.

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

"조커 박스"는 다른 박스와 상관없이 모든 스티커를 담을 수 있으므로, 여러 스티커가 혼합되어있는 상자는 그냥 조커박스로 쓰일 상자에 뭉쳐버리는 게 한가지 좋은 방법이 될 수 있다.

그러나, 단일 스티커 상자의 경우 "조커 박스"에 합치지 않아도 이미 정리가 된 상자로 볼 수 있기 때문에 단일 스티커 상자는 안에 들어있는 스티커별로 각각 1개씩은 "조커 박스"로 합치지 않아도 된다.

상자가 빈 상자라면 아무 계산도 하지 않고 넘기자.

이 관찰을 그대로 구현하면 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

bool visited[51];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int ans = 0;
	int N, M; cin >> N >> M;
	while (N--) {
		int type = 0;
		bool multitype = 0;
		for (int i = 1; i <= M; i++) {
			int x; cin >> x;
			if (x > 0) {
				if (type == 0) type = i;
				else multitype = 1;
			}
		}
		if (type == 0) continue;
		else if (multitype || visited[type]) ans++;
		else visited[type] = 1;
	}

	if (ans > 0) ans--;
	
	cout << ans;
}