[C++] 백준 1736번: 쓰레기 치우기 - Greedy

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

1736번: 쓰레기 치우기

---

 

4637번: Robots

위의 문제와 상당히 유사한 문제이다.

접근했던 방법은 로봇이 오른쪽과 아래만 움직일 수 있으므로 x나 y 방향으로 감소할 수 없다는 점을 이용했다.

 

만약 현재 로봇이 (4, 6)에 위치한다면 당연히 (4, 7) 또는 (5, 6)으로 이동을 할 것이고,

최소의 로봇 개수를 파악해야하므로 먼저 위에서부터 채우는 방식으로 접근했다.

 

무슨 의미냐면,

 

이렇게 다양한 방법이 있는 경우 전자의 경우를 생각한다는 의미이다.

 

이를 위해 어떻게 접근할까 고민하다가 사용한 방법은 우선순위 큐를 이용하는 것이고,

쓰레기의 위치의 좌표를 저장하여 현재 로봇의 위치와 비교하며 x, y모두 큰 순서로 현재 위치와 비교하면 된다.

 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

#include <iostream> #include <queue> using namespace std; using p=pair<int,int>; bool dp[101][101]; priority_queue<p, vector<p>, greater<p>>q, q2; int main(){     int n, m, x, y, curx=0, cury=0, cnt=0; cin >> n >> m;     for(int i=0; i<n; i++){         for(int j=0; j<m; j++){             cin >> dp[i][j];             if(dp[i][j]) q.push({i,j});         }     }     while(!q.empty()){         while(!q.empty()){             x=q.top().first, y=q.top().second; q.pop();             if(x>=curx && y>=cury) curx=x, cury=y;             else q2.push({x,y});         }         cnt++;         curx=cury=0;         while(!q2.empty()) q.push(q2.top()), q2.pop();     }     cout << cnt; } Colored by Color Scripter

cs