[BOJ/C++] 1736 - 쓰레기 치우기

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

 

---

 

알고리즘 동아리 시간에 고민하다가 결국 못풀었던 문제.

처음 고민할땐 DP로 풀릴거같아서 어떻게든 점화식을 세워 보려고 했었는데.. 잘 안되더라;

그리고 점화식 고민하면서 DP인것도 의심이 들었던게, 시간제한이 2초나 되고, N,M이 최대 100밖에 안돼서.. 확신이 안섰다..

(조금 직접적인) 힌트를 들어도 이해가 안됐다가, 다행히 다음날에 번뜩 아이디어가 떠올라서 풀었더니 AC !

 

 

일단, 로봇의 움직임은 문제에서 나왔다시피 아래쪽 또는 오른쪽 둘 중 하나이다.

최소의 로봇을 사용하므로, 하나의 로봇이 최대한 많은 쓰레기를 치워야 한다. 

따라서 모든 쓰레기를 치우기 위해선, 어떤 로봇은 가장 위, 가장 왼쪽에 위치한 쓰레기에 도달해야하고, 그 위치에 도달한 로봇은 로봇의 현재위치 {i,j} ~ {n-1,m-1}에 해당하는 구간에서 가장 위, 가장 왼쪽에 위치한 쓰레기에 마찬가지로 도달해야하고, 마지막으로 {n-1,m-1}에 도달할 것이다. 이렇게 하면 한 로봇이 최대한 많은 쓰레기를 집을 수 있게 된다.

 

그럼 위의 방식으로 재귀적으로 탐색하면 될 것 같다!

여기서 의심이 되는 건 시간복잡도인데, 한 로봇이 치울 수 있는 쓰레기의 최대 개수는 n+m-1. 즉, 최대 재귀 호출 깊이는 n+m-1이고, 재귀함수 내에서 가장 위, 가장 왼쪽 쓰레기를 찾기 위해 O(n*m)시간이 소요된다.(재귀 깊이가 깊어질수록 소요시간이 줄긴 하지만, 조금 넉넉하게 계산해보자.). 그리고 로봇의 최대 수는 min(n,m)개이므로, 

따라서 O( min(n,m) * n*m * (n+m-1) ).

n과 m은 최대 100이니까, 계산해보면 1억 좀 안된다.

시간복잡도 계산을 넉넉하게 계산했으므로 시간내에는 충분히 돌아간다!

 

이 문제로 재귀+그리디 문제는 처음 접해보는 것 같다. 되게 낯선데 문제가 재미있어서 포스팅 해 본다!

 

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(int i=x;i<y;i++)
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*----------------------*/

int n,m;
int board[101][101];
int cnt;
void f(pii loc){
    rep(i,loc.X,n) rep(j,loc.Y,m){
        if(board[i][j]==1){
            board[i][j] = 0;
            cnt--;
            f({i,j});
            return;
        }
    }
    return;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    rep(i,0,n) rep(j,0,m){
        cin>>board[i][j];
        if(board[i][j]==1) cnt++;
    }

    int ans = 0;
    while(cnt){
        f({0,0});
        ans++;
    }
    cout<<ans<<'\n';

}