www.acmicpc.net/problem/2304
이건 알고리즘 공부하기 전에 말도 안 되게 짰다가
틀려서 다시 오랜만에 시도한 문제이다.
c++ 중에 map이라는 걸 사용할 것이다.
map은 key값과 value가 한 쌍으로 되어있는 컨테이너이다.
알고리즘
1. map에 넣는다 (위치, 높이)
1-1). map에 넣으면서 높이가 젤 큰 값을 구한다. (위치도 젤 큰 값)
1-2). map에 넣으면서 마지막 위치를 구한다.
2. iterater를 이용하여 map의 젤 앞의 위치와 높이를 저장하고 iter를 map의 두 번째 위치로 바꾼다.
3. iter를 1-1)에서 구한 젤 큰 위치 값까지 for을 돌린다.
3-1). 앞의 높이가 현재 가리키고 있는 iter의 높이보다 작거나 같으면
사각형의 넓이를 더해준다.
앞의 위치를 현재 위치, 앞의 높이를 현재 높이로 대입한다.
4. 젤 큰 값은 앞의 for문으로 돌리지 않았기 때문에 높이만 더해준다(넓이가 1이라서)
5. iter를 lower_bound를 이용하여 1-2)에서 구한 마지막 위치로 가리킨다.
6. iter를 이용하여 젤 뒤의 위치와 높이를 저장하고 iter를 map의 뒤에서 두번째 위치로 바꾼다.
7. iter를 1-1)에서 구한 젤 큰 위치 값까지 for문 돌린다.
7-1). 뒤의 높이가 현재 가리키고 있는 iter의 높이보다 작으면
사각형의 넓이를 더해준다.
뒤의 위치를 현재위치, 뒤의 높이를 현재 높이로 대입한다.
8. 넓이를 출력
위 그림식으로 끝에서 젤 큰 높이를 향하여 더해준다.
이 문제에서의 반례는
이러한 상황이다. 최대의 높이가 두개 이상일 경우,
이 반례를 생각하지 않는다면 최대 높이만 구하여한다면 틀린다.
나도 그렇게 틀렸었다.
소스 코드
#include<iostream>
#include<map>
using namespace std;
int main() {
map<int, int> m;
int testcase;
int row, hight;
int max_row = 0, max_hight = 0;
int sum = 0;
int last_row = 0;
cin >> testcase;
while (testcase--) {
cin >> row >> hight;
m.insert(pair<int, int>(row, hight));
if (max_hight <= hight) {
max_hight = hight;
max_row = row;
}
if (last_row < row) {
last_row = row;
}
}
map<int, int>::iterator iter;
iter = m.begin();
int my_row = iter->first;
int my_hight = iter->second;
iter++;
for (; my_row != max_row; iter++) {
if (my_hight <= iter->second) {
sum += (iter->first - my_row) * my_hight;
my_row = iter->first;
my_hight = iter->second;
}
}
sum += my_hight;
iter = m.lower_bound(last_row);
my_row = iter->first;
my_hight = iter->second;
iter--;
for (; my_row != max_row; iter--) {
if (my_hight <= iter->second) {
sum += (my_row - iter->first) * my_hight;
my_row = iter->first;
my_hight = iter->second;
}
}
cout << sum;
return 0;
}