이 문제는 내가 완전 감을 잘못 잡고 풀고 있었다. 이 문제를 증가수열 비슷하게 풀려고 했었다 하지만 이렇게 풀면 로직이 꼬였는데 테스트케이스 몇개는 잘나왔으나 몇개는 매우 잘 나오지 않았다.
이 문제의 로직은 현재 나를 기준으로 내왼쪽에서의 최대높이와 내오른 쪽의 최대높이를 비교해서 낮은 높이를 선택 해주는 문제 였다 단 오른쪽 과 왼쪽의 최대높이가 나보다는 클때만 빗물이 받아지니 해당 상황일때만 계산하도록 코드를 작성한다 그림으로 나타내면 대충 아래와 같다
해당 로직에 대한 코드는 아래 와 같다
#include <iostream>
#include<algorithm>
using namespace std;
int h, w;
int arr[500];
int main() {
cin >> h >> w;
int result = 0;
for (int i = 0; i < w; i++) {
cin >> arr[i];
}
for (int i = 1; i < w - 1; i++) {
int lmax = 0;
int rmax = 0;
for (int j = 0; j < i; j++) {
if (lmax < arr[j] && arr[j]>arr[i])
lmax = arr[j];
}
for (int j = i + 1; j < w; j++) {
if (rmax < arr[j] && arr[j]>arr[i])
rmax = arr[j];
}
if (lmax != 0 && rmax != 0)
result += min(lmax, rmax) - arr[i];
}
cout << result;
}
정확히 이문제는 핵심이 나를 기준으로 나보다 크기가 작고 같은 거리에 있는 물고기 들은 위에에서 왼쪽부터 오른쪽 까지 검사하고 내려와서 왼쪽부터 오른쪽 까지 검사하면서 이 순으로 탐색을 하는 거였다. 단 위에를 듣고 BFS 이동방향을 1,0 ->0,-1 ->0,1 ->-1,0 이렇게 만 하면 안풀린다
핵심은 이부분이다 내가 물고기를 먹을 수있는 지역으로 갔을 때 현재 큐에 들어와 있는 것중 나보다 거리가 작거나 같고 행의 값이 위에 있거나 혹은 행이 같다면 열값이 더 먼저인 애를 찾아서 거기를 가야한다 이에 의해 필자는 행을 검사에서 위에있으면 해당 행으로 탐색지점을 바꿔줬고 같다면 열값이 더 작은 쪽으로 옮겨줬다
#include <iostream>
#include <queue>
using namespace std;
int n;
int arr[20][20] = { 0, };
bool isVisited[20][20];
int fishSize = 2;
int eatFish = 0;
int cnt = 0;
queue<pair<int,pair<int, int>>> bfsQ;
bool CanEat(int x, int y) {
if (arr[x][y]>0&&arr[x][y] < fishSize) {
return true;
}
return false;
}
bool canGo(int x, int y) {
if (x >= 0 && x < n && y >= 0 && y < n && !isVisited[x][y] && (CanEat(x, y) || arr[x][y] == 0 || arr[x][y]==fishSize))
return true;
else
return false;
}
void Bfs(int x, int y) {
bfsQ.push({ cnt,{x,y} });
arr[x][y] = 0;
int startX, startY, cost;
int otherX, otherY, otherCost;
while (!bfsQ.empty()) {
startX = bfsQ.front().second.first;
startY = bfsQ.front().second.second;
cost = bfsQ.front().first;
bfsQ.pop();
if (CanEat(startX, startY)) {
cnt += cost;
while (!bfsQ.empty()) {
otherX = bfsQ.front().second.first;
otherY = bfsQ.front().second.second;
otherCost = bfsQ.front().first;
if (CanEat(otherX, otherY) && otherCost<=cost) {
if (otherX < startX) {
startX = otherX;
startY = otherY;
otherCost = cost;
}
else if (otherX == startX && startY>otherY ) {
startX = otherX;
startY = otherY;
otherCost = cost;
}
}
bfsQ.pop();
}
bfsQ.push({ 0, {startX, startY}});
eatFish += 1;
if (eatFish == fishSize) {
fishSize += 1;
eatFish = 0;
}
arr[startX][startY] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
isVisited[i][j] = false;
}
}
isVisited[startX][startY] = true;
cost = 0;
}
if (canGo(startX-1,startY)) {
bfsQ.push({ cost + 1,{startX -1,startY}});
isVisited[startX - 1][startY] = 1;
}
if (canGo(startX, startY-1)) {
bfsQ.push({ cost + 1,{startX ,startY - 1} });
isVisited[startX][startY-1] = 1;
}
if (canGo(startX , startY+1)) {
bfsQ.push({ cost + 1,{startX ,startY + 1} });
isVisited[startX][startY + 1] = 1;
}
if (canGo(startX+1 , startY)) {
bfsQ.push({ cost + 1,{startX + 1,startY} });
isVisited[startX + 1][startY] = 1;
}
}
}
int main() {
cin >> n;
int startIdxCol, startIdxRow;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
if (arr[i][j] == 9) {
startIdxCol = i;
startIdxRow = j;
}
}
}
Bfs(startIdxCol, startIdxRow);
cout << cnt;
}
이 문제의 경우 흐름대로 생각하면 그게 정답이다 단 주의 할점은 단지 하나의 priority queue로 만한다면 음수부분의 처리가 이상하게 될것이다 이에 나는 음수와 0을 저장하는 priority queue와 양수만을 저장해주는 priority queue로 작성하였으며 음수 와 0을 묶은 이유는 음수와 음수의 곱은 양수이고 만약 음수와 0만 큐에 남았을 때는 2개를 곱하여 0을 반환함으로 작은 값을 반환할거라고 생각했다
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
priority_queue<int> plusNum;
priority_queue<int,vector<int>, greater<int>> negativeNum;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int temp1;
cin >> temp1;
if (temp1 > 0) {
plusNum.push(temp1);
}
else {
negativeNum.push(temp1);
}
}
int sum = 0;
while (!plusNum.empty())
{
int num1, num2;
num1 = plusNum.top();
plusNum.pop();
if (plusNum.empty()) {
sum += num1;
break;
}
num2 = plusNum.top();
plusNum.pop();
if (num1 != 1 && num2 != 1) {
sum += num1 * num2;
}
else {
sum += num1 + num2;
}
}
while (!negativeNum.empty())
{
int num1, num2;
num1 = negativeNum.top();
negativeNum.pop();
if (negativeNum.empty()) {
sum += num1;
break;
}
num2 = negativeNum.top();
negativeNum.pop();
sum += num1 * num2;
}
cout << sum;
}
이 문제의 경우 Priority Queue를 사용하지 않으면 시간 초과 가 발생한다 이문제의 핵심은 작은 가방에 담을수 있는 가장 큰걸 담고 그다음크기의 가방에 그 가방의 크기에 담을 수 있는것중 가장 큰것을 담으면 된다. 이 로직을 구현하기 위해서는 일차적으로 가장 작은 무게에 담을 수 있는 모든 물건들을 선택한다 거기서 가장 큰 애를 선택한다. 이차적으로 이전에 담고 남은 물건들중에 두번째 무게에 담을 수 있는 모든 물건들을 모두 고른 후 이전 애 고른애들과 합쳐서 놓은 다음 그중에 큰거를 고르면 된다.
이 로직에서 일단 필요한건 우선순위 큐다. 일차적으로 가방을 작은 순으로 나열해서 가장 작은 가방에 담을 수 있는 애를 우선순위큐에 담는다 보석들도 무게순으로 정렬 되어 있다 그래서 첫번째 가방에 담으면 첫번째 가방에 담긴 마지막 인덱스 이후로 무게가 큰 보석들이 남는다 그중 두번째 가방에 닿을 수 있는 물건들을 담아서 우선순위 큐에 넣는다. 거기서 최고 큰값을 선택 한다
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
priority_queue<int> pq;
int bag[300000];
pair<int, int> jewerly[300000];
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) {
int temp1, temp2;
cin >> temp1 >> temp2;
jewerly[i] = { temp1,temp2 };
}
for (int i = 0; i < k; i++) {
cin >> bag[i];
}
sort(jewerly, jewerly + n);
sort(bag, bag + k);
int idx=0;
long long sum = 0;
for (int i = 0; i < k; i++) {
while (idx < n && bag[i] >= jewerly[idx].first) {
pq.push(jewerly[idx].second);
idx++;
}
if (!pq.empty()) {
sum += pq.top();
pq.pop();
}
}
cout << sum;
}
