이것도 알아야 하네?
[C++] 백준 11997번: Load Balancing (Silver) 본문
문제
https://www.acmicpc.net/problem/11997
풀이
(1차 시도)
설명
해당 문제는 맵을 그리기 위한 사이즈를 사전에 알 수 없기 때문에 값을 받은 후 계산해야한다. 첫 번째 시도에서는 해당 사이즈를 구하는 방법으로 가장 외곽에 있는 소를 찾았다. 생각해보면, 아래의 그림처럼 외곽 뿐만 아니라 가장 내곽에 있는 소 위치도 찾아서 맵 사이즈를 구했어야했는데, 코드 작성할 당시에는 밖에 부분만 생각했던 것 같다. 아래의 코드에서는 한 마리의 소가 (1000,1000)에 존재하더라도 1000x1000의 메모리할당을 하게 되어있다.
아무튼, 할당한 후에는 "누적 합"을 2d에 이용해서 현재 위치까지의 소 마리 수를 구한다. 즉, map[i][j]는 (0,0)부터 (i,j)까지 존재하는 소의 수량이다. fence가 (i,j)에 존재할 떄 fence 이후에 존재하는 소의 수량을 구하고 싶으면, 가로축에 존재하는 소 수량을 나타내는 map[i][_size]에서 (i,j)까지의 소 수량을 나타내는 map[i][j]을 뺴주면 아래의 주황색 영역에 존재하는 소 수량만 구할 수 있다. 이때 주의할 점은 fence를 축으로 했을 때 4 사분면에 있는 소를 구할 때는 아래의 코드의 bottomRight = map[_size][_size] - map[_size][j] - map[i][_size] + map[i][j]; 처럼 구해야한다. map[i][j]를 한 번 더해줘야하는 이유는 map[_size][j]와 map[i][_size]에 모두 map[i][j]가 포함되어 두 번 빼지기 때문이다.
코드
#include <string>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
vector<vector<int>> map;
int main() {
int N;
int _size = INT_MIN;
scanf("%d", &N);
int x, y;
vector<pair<int, int>> vec;
for (int i = 0; i < N; i++) {
scanf("%d %d", &x, &y);
vec.push_back({x, y});
_size = x > _size ? x : _size;
_size = y > _size ? y : _size;
}
map.assign(_size+1, vector<int>(_size+1, 0));
for (int i = 0; i < N; i++) {
map[vec[i].second-1][vec[i].first-1] = 1;
}
/*cumulative sum*/
/* accumulate = left to right */
for (int i = 0; i < _size+1; i++) {
for (int j = 0; j < _size; j++) {
map[i][j+1] += map[i][j];
}
}
/* accumulate = left to right */
for (int i = 0; i < _size; i++) {
for (int j = 0; j < _size+1; j++) {
map[i+1][j] += map[i][j];
}
}
int ans=INT_MAX;
for (int i = 1; i < _size; i+=2) {
for (int j = 1; j < _size; j+=2) {
int topLeft = map[i][j];
int topRight = map[i][_size] - map[i][j];
int bottomLeft = map[_size][j] - map[i][j];
int bottomRight = map[_size][_size] - map[_size][j] - map[i][_size] + map[i][j];
ans = min(ans, max({topLeft, topRight, bottomLeft, bottomRight}));
}
}
printf("%d", ans);
}
결과
아니나 다들까 메모리 초과가 나왔다.
(2차 시도)
설명
메모리를 줄이는 방법을 고민해보았을 때, 사실 소가 존재하지 않는 공간은 필요가 없다. 그렇기 떄문에 현재 있는 소들의 위치를 다시 정의하여 map을 다시 구했다. 1차 시도와 동일한 방식으로 구하면 된다.
코드
#include <string>
#include <vector>
#include <algorithm>
#include <limits.h>
#include <map>
using namespace std;
vector<vector<int>> cum;
map<int, int> idx_x;
map<int, int> idx_y;
int main() {
int N;
scanf("%d", &N);
int x, y;
vector<pair<int, int>> vec;
vector<int> temp_x;
vector<int> temp_y;
for (int i = 0; i < N; i++) {
scanf("%d %d", &x, &y);
vec.push_back({x, y});
temp_x.push_back(x);
temp_y.push_back(y);
}
sort(temp_x.begin(), temp_x.end());
int cnt = 0;
for (int i = 0; i < N; i++) {
if (idx_x.find(temp_x[i]) == idx_x.end()) { // not in
idx_x.insert({temp_x[i], cnt});
cnt++;
}
}
sort(temp_y.begin(), temp_y.end());
cnt = 0;
for (int i = 0; i < N; i++) {
if (idx_y.find(temp_y[i]) == idx_y.end()) { // not in
idx_y.insert({temp_y[i], cnt});
cnt++;
}
}
int _size = max(idx_x.size(), idx_y.size());
cum.assign(_size, vector<int>(_size, 0));
for (int i = 0; i < N; i++) {
x = vec[i].first;
y = vec[i].second;
int new_x = idx_x.find(x)->second;
int new_y = idx_y.find(y)->second;
cum[new_y][new_x]++;
}
/* cumulative sum */
// left to Right
for (int i = 0; i < _size; i++) {
for (int j = 1; j < _size; j++) {
cum[i][j] += cum[i][j-1];
}
}
// Top to Bottom
for (int i = 1; i < _size; i++) {
for (int j = 0; j < _size; j++) {
cum[i][j] += cum[i-1][j];
}
}
int ans=INT_MAX;
for (int i = 0; i < _size; i++) {
for (int j = 0; j < _size; j++) {
int topLeft = cum[i][j];
int topRight = cum[i][_size-1] - cum[i][j];
int bottomLeft = cum[_size-1][j] - cum[i][j];
int bottomRight = cum[_size-1][_size-1] - cum[_size-1][j] - cum[i][_size-1] + cum[i][j];
ans = min(ans, max({topLeft, topRight, bottomLeft, bottomRight}));
}
}
printf("%d", ans);
}
결과
'프로그래밍 > 알고리즘' 카테고리의 다른 글
[C++] 백준 14462번: 소가 길을 건너간 이유 8 (0) | 2022.06.22 |
---|---|
[C++] 백준 11993번: Circular Barn (Gold) (0) | 2022.05.17 |
[C++] 백준 14465번: 소가 길을 건너간 이유 5 (1) | 2022.03.23 |
[C++] 백준 11996번: Circular Barn (Silver) (1) | 2022.03.23 |
[C++] 백준 11967번: 불켜기 (1) | 2022.03.03 |