[ boj : 1736 ] 쓰레기 치우기

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

1736번: 쓰레기 치우기

문제 : 쓰레기가 격자판에 주어지고 로봇은 쓰레기를 치워야 합니다. 이때 로봇은 오른쪽,아래로만 이동할 수 있습니다. 최소 로봇의 개수를 구하시오

해설 : 아,,,,,너무 어렵습니다 ㅠㅠㅠㅠ 그냥 단순한 디피나 dfs 라고 생각했는데 그게 아니었어요,,,

일단 단순히 dp로만 풀기에는 로봇의 개수를 매 동작마다 업데이트 칠수 있는 방법이 떠오르질 않았습니다. 그래서 전 도움을 받았네요

한 로봇이 쓰레기를 최대로 치울 수 있는 방법은 로봇이 이동하는 경로에 쓰레기가 존재하면 되겠죠. 그리고 이를 만족하기 위한 조건은 (x,y)에 쓰레기가 존재하고 로봇이 치웠다고 생각할때 이 로봇이 다음 쓰레기를 치울 수 있는 방법은 x이하 y이상인 곳에 쓰레기가 존재하면 됩니다.

허접한 그림을 가지고 설명하겠습니다.

빨강 : 쓰레기가 위치해 있고 로봇이 이곳에 도달하여 치운상태

파랑 : 로봇이 다음 쓰레기를 치울 수 있는 범위

노랑 : 만약 파란색으로 간다면 새로운 로봇이 와서 치워야될 자리

즉, 로봇이 (x,y) 자리에서 치웠다면 이 로봇이 최대한 치울 수 있는 자리는 현재 y좌표보다 큰 쓰레기들 중에서 x좌표보다 아래인 쓰레기를 치울 수 있습니다. 한행은 한 로봇이 다 치울 수 있으니까요. 그리고 또 위의 작업을 반복하는 것입니다. 더이상 x이하 y이상인 좌표들 중에 쓰레기가 존재하지 않을때 까지

#include <bits/stdc++.h>
using namespace std;

int a[105][105];
vector<int> v[105];

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

	int n, m;
	cin >> n >> m;
	int cnt = 0, ans = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			cin >> a[i][j];
			if (a[i][j])
				v[i].push_back(j), cnt++;
		}
	while (cnt)
	{
		ans++;
		int x = 0;
		for (int i = 0; i < n; i++)
		{
			auto p = lower_bound(v[i].begin(), v[i].end(), x);
			if (p == v[i].end())
				continue;

			x = v[i].back();
			while (!v[i].empty() && v[i].back()>=(*p)) {
				v[i].pop_back();
				cnt -= 1;
			}

		}
	}
	cout << ans;
}