[SW Expert Academy] D3 1206. View(c++)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	for (int i = 0; i < 10; i++) {
		vector<int> buildings;
		vector<int> leftside;
		int n, building;
		cin >> n;
		pair<int, int> side = { 0, 0 };
		for (int j = 0; j < n; j++) {
			cin >> building;
			buildings.push_back(building);
			leftside.push_back(building - max(side.first, side.second));
			if (leftside.back() < 0) leftside.back() = 0;
			side.second = side.first;
			side.first = building;
		}

		int temp = 0, result = 0;
		side = { 0, 0 };
		for (int j = n-1; j >= 0; j--) {
			temp = buildings[j] - max(side.first, side.second);
			side.second = side.first;
			side.first = buildings[j];
			if (temp < 0) continue;
			if (temp < leftside[j]) result += temp;
			else result += leftside[j];
		}

		cout << "#" << i + 1 << " " << result << '\n';
	}
	return 0;
}

---

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

728x90

---

[접근 1]

왼쪽이 막혔는지 확인하는 과정이다.

building의 높이를 받아오며 buildings에 저장해둔다.

pair에 바로 왼쪽에 있는 칸의 높이, 왼쪽으로 두번째에 있는 칸의 높이를 가지고 있다.

둘 중에 큰 값을 현재 위치의 빌딩의 높이에서 빼서 leftside라는 vector에 넣어준다.

그럼 leftside 벡터에는 왼쪽이 막혀있지 않은 칸의 수를 알 수 있다.

vector<int> buildings;
vector<int> leftside;
int n, building;
cin >> n;
pair<int, int> side = { 0, 0 };
for (int j = 0; j < n; j++) {
    cin >> building;
    buildings.push_back(building);
    leftside.push_back(building - max(side.first, side.second));
    if (leftside.back() < 0) leftside.back() = 0;
    side.second = side.first;
    side.first = building;
}

---

[접근 2]

같은 방법으로 오른쪽이 막혀있지 않은 칸의 수를 구하는 동시에

시간을 아끼기 위하여 leftside와 비교하여 더 적게 남은 칸의 수를 result에 더해준다.

int temp = 0, result = 0;
side = { 0, 0 };
for (int j = n-1; j >= 0; j--) {
    temp = buildings[j] - max(side.first, side.second);
    side.second = side.first;
    side.first = buildings[j];
    if (temp < 0) continue;
    if (temp < leftside[j]) result += temp;
    else result += leftside[j];
}