[백준] 2304 창고 다각형 c++

www.acmicpc.net/problem/2304

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;
}