[백준] 6198 옥상 정원 꾸미기 - C++

https://www.acmicpc.net/problem/6198

---

로직을 짜려고 엄청 노력했다..

금단의 방법인 그림 그리기까지 써가며 풀었다.

문제를 이해하는 방식을 바꾸어야 한다.

높은 빌딩에서 자신보다 낮은 빌딩의 수를 세는 게 아니라

낮은 빌딩에서 자신을 볼 수 있는 높은 빌딩의 수를 세어주어야 한다.

 

stack을 top부터 뽑아가며,

top이 자신보다 낮다면? -> 자신을 볼 수 없으니 pop

top이 자신보다 높다면? -> top아래의 것들도 자신보다 높을 테니

자신보다 높은 빌딩의 수인 stack의 size(들어있는 원소의 개수)를 result에 더하고 자신을 push

 

위 로직대로 코드를 짰다.

빌딩의 개수와 높이가 딱 봐도 커서 맘 편하게 long long int를 사용했다.

---

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
int main() {
	long long int result = 0;
	stack<int> stk;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int input;
		cin >> input;
		while (!stk.empty()) {
			if (stk.top() > input) {
				result += stk.size();
				break;
			}
			stk.pop();
		}
		stk.push(input);
	}
	cout << result;
	return 0;
}

 

---

 

 

사실 stack을 사용해서 풀기 전에, stack을 안 쓰고도 풀 수 있을 것 같아서

메모이제이션으로 푼 방법이 있긴 하다.

빌딩을 오른쪽부터 선택해서 자신이 볼 수 있는 빌딩의 개수를 메모하고.. 이런 식으로 진행된다.

어휘력이 안 좋으니 차근차근 읽기를 바란다..

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
	vector<int> height;
	long long int result = 0;
	int n;
	cin >> n;
	vector<int> memo(n, 0);
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		height.push_back(tmp);
	}
	for (int i = n - 2; i >= 0; i--) {
		int cur = i;
		memo[cur] = 0;
		int j = cur + 1;
		while (j < n && height[cur] > height[j]) {
			memo[cur] += memo[j] + 1; // <1>
			j += memo[j] + 1; // <2>
		}
		result += memo[cur];
	}
	cout << result << endl;
	return 0;
}

입력받은 빌딩의 높이를 저장할 벡터 height,

index번째 빌딩에서 볼 수 있는 빌딩의 수를 메모하는 벡터 memo(0으로 초기화됨)를

선언해 주었다.

 

첫 번째 for문은 그저 값을 입력받는 용도이다.

두 번째 for문은 height 벡터의 값을 오른쪽부터 선택하게 한다. = 오른쪽부터 왼쪽 빌딩을 차례로 선택한다.

현재 선택한 index를 알아보기 쉽게 cur로 새로 선언한다.

j는 cur번째 빌딩에서 바라볼 수 있는 빌딩의 index이다. (일단 cur번째 빌딩 바로 앞 빌딩의 index로 잡는다.)

 

while문의 조건식은 j가 벡터의 범위 안에 있게 하고, j번째 빌딩이 cur번째 빌딩보다 작을 때에만 이하의 코드를 실행하게 한다.

<1> : cur번째 빌딩이 볼 수 있는 건물 수에다가 j번째 건물이 볼 수 있는 건물 수 + 1을 더한다.

--->>> 왜냐하면, j번째 빌딩은 cur번째 빌딩보다 낮아서(while문 조건을 통과했으니) j번째 빌딩이 볼 수 있는 빌딩은 cur번째 빌딩도 볼 수 있다. 또한 cur번째 빌딩은 j번째 빌딩도 포함해서 볼 수 있으므로 + 1 해주었다.

<2> : j(index를 나타냄)에 j가 볼 수 있는 값 + 1을 더해준다.

--->>> 왜냐하면, j번째 빌딩이 볼 수 "없는" 빌딩을, cur번째 빌딩은 볼 수 있을 수도 있기 때문이다.

따라서 j번째 빌딩이 볼 수 있는 빌딩의 수 + 1 값을 j값에 더해 while문 조건을 한번 더 검사시킨다.

(j값을 알맞은 위치로 점프시킨다? 고 생각하면 될 것 같다.)

 

이후 현재 선택한 빌딩이 볼 수 있는 빌딩의 수를 result에 더하고,

모든 빌딩을 돌았다면 result를 출력한다.

---

처음부터 stack 썼으면 편하게 풀었을 것을

괜히 오기 부려서 오래 걸린 것 같다.........

---